5 people like it.
Like the snippet!

Combinatorial functions

Here is my F# take on some combinatorial functions from the book "Introduction to Functional Programming" by Richard Bird and Philip Wadler.

Combinatorial functions

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
65: 
66: 
67:

// Combinatorial functions from the book "Introduction to Functional Programming"
// by Richard Bird and Philip Wadler.

// the function inits returns the list of all inital segments of a list, 
// in order of increasing length.
let rec inits = function
    | []    -> [[]]
    | x::xs -> [ yield [];
                 for ys in inits xs do
                    yield! [x::ys]]
// Example:
// > inits [1..5];;
// val it : int list list =
//  [[]; [1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]]

// the function subs returns a list of all subsequences of a list
let rec subs = function
    | [] -> [[]]
    | x::xs -> [ for ys in subs xs do
                    yield! [ys;x::ys] ]
// > subs [1..3];;
// val it : int list list =
//   [[]; [1]; [2]; [1; 2]; [3]; [1; 3]; [2; 3]; [1; 2; 3]]

// the term interleave x ys returns a  list of all possible ways of inserting 
// the element x into the list ys.
let rec interleave x = function
    | [] -> [[x]]
    | y::ys -> 
        [ yield x::y::ys
          for zs in interleave x ys do
            yield! [y::zs]]

// Example: 
// > interleave "" ["Count"; "Of"; "Monte"; "Cristo"];;
// val it : string list list =
//   [[""; "Count"; "Of"; "Monte"; "Cristo"];
//    ["Count"; ""; "Of"; "Monte"; "Cristo"];
//    ["Count"; "Of"; ""; "Monte"; "Cristo"];
//    ["Count"; "Of"; "Monte"; ""; "Cristo"];
//    ["Count"; "Of"; "Monte"; "Cristo"; ""]]

// the function perms returns a list of all permutations of a list.
let rec perms = function
    | [] -> [[]]
    | x::xs -> List.concat (List.map (interleave x) (perms xs))

// > perms [1..3];;
// val it : int list list =
//   [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]

// some helper functions
let curry f a b = f(a,b)
let cons x = curry List.Cons x

// the function parts returns a list of all proper partitions of a list.    
let rec parts = function
    | []    -> [[]]
    | [x]   -> [[[x]]]
    | x::x'::xs -> List.map (glue x) (parts (x'::xs)) 
                    @ List.map (cons [x]) (parts (x'::xs))

and glue x xss = (x :: List.head xss):: List.tail xss

// > parts [1..3];;
// val it : int list list list =
//   [[[1; 2; 3]]; [[1; 2]; [3]]; [[1]; [2; 3]]; [[1]; [2]; [3]]]

val inits : _arg1:'a list -> 'a list list

Full name: Script.inits

val x : 'a

val xs : 'a list

val ys : 'a list

val subs : _arg1:'a list -> 'a list list

Full name: Script.subs

val interleave : x:'a -> _arg1:'a list -> 'a list list

Full name: Script.interleave

val y : 'a

val zs : 'a list

val perms : _arg1:'a list -> 'a list list

Full name: Script.perms

Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>

val concat : lists:seq<'T list> -> 'T list

Full name: Microsoft.FSharp.Collections.List.concat

val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map

val curry : f:('a * 'b -> 'c) -> a:'a -> b:'b -> 'c

Full name: Script.curry

val f : ('a * 'b -> 'c)

val a : 'a

val b : 'b

val cons : x:'a -> ('a list -> 'a list)

Full name: Script.cons

static member List.Cons : head:'T * tail:'T list -> 'T list

val parts : _arg1:'a list -> 'a list list list

Full name: Script.parts

val x' : 'a

val glue : x:'a -> xss:'a list list -> 'a list list

Full name: Script.glue

val xss : 'a list list

val head : list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.head

val tail : list:'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.tail

Next Version Raw view Test code New version

More information

Link:	http://fssnip.net/48
Posted:	13 years ago
Author:	Cesar Mendoza
Tags:	combinatorial functions , mathematics , recursion , permutations , combinatorial