## Combinatorial functions

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

Tools:

### Combinatorial functions

``` 1: // Combinatorial functions from the book "Introduction to Functional Programming"
2: // by Richard Bird and Philip Wadler.
3:
4: // the function inits returns the list of all inital segments of a list,
5: // in order of increasing length.
6: let rec inits = function
7:     | []    -> [[]]
8:     | x::xs -> [ yield [];
9:                  for ys in inits xs do
10:                     yield! [x::ys]]
11: // Example:
12: // > inits [1..5];;
13: // val it : int list list =
14: //  [[]; [1]; [1; 2]; [1; 2; 3]; [1; 2; 3; 4]; [1; 2; 3; 4; 5]]
15:
16: // the function subs returns a list of all subsequences of a list
17: // this function is also know as the powerset.
18: let rec subs = function
19:     | [] -> [[]]
20:     | x::xs -> [ for ys in subs xs do
21:                     yield! [ys;x::ys] ]
22: // > subs [1..3];;
23: // val it : int list list =
24: //   [[]; [1]; [2]; [1; 2]; [3]; [1; 3]; [2; 3]; [1; 2; 3]]
25:
26: // the term interleave x ys returns a  list of all possible ways of inserting
27: // the element x into the list ys.
28: let rec interleave x = function
29:     | [] -> [[x]]
30:     | y::ys ->
31:         [ yield x::y::ys
32:           for zs in interleave x ys do
33:             yield! [y::zs]]
34:
35: // Example:
36: // > interleave "" ["Count"; "Of"; "Monte"; "Cristo"];;
37: // val it : string list list =
38: //   [[""; "Count"; "Of"; "Monte"; "Cristo"];
39: //    ["Count"; ""; "Of"; "Monte"; "Cristo"];
40: //    ["Count"; "Of"; ""; "Monte"; "Cristo"];
41: //    ["Count"; "Of"; "Monte"; ""; "Cristo"];
42: //    ["Count"; "Of"; "Monte"; "Cristo"; ""]]
43:
44: // the function perms returns a list of all permutations of a list.
45: let rec perms = function
46:     | [] -> [[]]
47:     | x::xs -> List.concat (List.map (interleave x) (perms xs))
48:
49: // > perms [1..3];;
50: // val it : int list list =
51: //   [[1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]
52:
53: // some helper functions
54: let curry f a b = f(a,b)
55: let cons x = curry List.Cons x
56:
57: // the function parts returns a list of all proper partitions of a list.
58: let rec parts = function
59:     | []    -> [[]]
60:     | [x]   -> [[[x]]]
61:     | x::x'::xs -> List.map (glue x) (parts (x'::xs))
62:                     @ List.map (cons [x]) (parts (x'::xs))
63:
64: and glue x xss = (x :: List.head xss):: List.tail xss
65:
66: // > parts [1..3];;
67: // val it : int list list list =
68: //   [[[1; 2; 3]]; [[1; 2]; [3]]; [[1]; [2; 3]]; [[1]; [2]; [3]]]
69:
70: // This one comes from the book "Programming in Haskell" by Graham Hutton.
71: // The function choices returns all the way you can select elements from a list
72: let choices xs = List.concat (List.map perms (subs xs))
73:
74: // > choices [1..3];;
75: // val it : int list list =
76: //   [[]; [1]; [2]; [1; 2]; [2; 1]; [3]; [1; 3]; [3; 1]; [2; 3]; [3; 2];
77: //    [1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]]```
val inits : 'a list -> 'a list list

Full name: Snippet.inits
val x : 'a
val xs : 'a list

type: 'a list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a>
implements: System.Collections.IEnumerable
val ys : 'a list

type: 'a list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a>
implements: System.Collections.IEnumerable
val subs : 'a list -> 'a list list

Full name: Snippet.subs
val interleave : 'a -> 'a list -> 'a list list

Full name: Snippet.interleave
val y : 'a
val zs : 'a list

type: 'a list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a>
implements: System.Collections.IEnumerable
val perms : 'a list -> 'a list list

Full name: Snippet.perms
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------

type List<'T> =
| ( [] )
| ( :: ) of 'T * 'T list
with
interface System.Collections.IEnumerable
interface System.Collections.Generic.IEnumerable<'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
end

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

type: List<'T>
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'T>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'T>
implements: System.Collections.IEnumerable
val concat : seq<'T list> -> 'T list

Full name: Microsoft.FSharp.Collections.List.concat
val map : ('T -> 'U) -> 'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val curry : ('a * 'b -> 'c) -> 'a -> 'b -> 'c

Full name: Snippet.curry
val f : ('a * 'b -> 'c)
val a : 'a
val b : 'b
val cons : 'a -> ('a list -> 'a list)

Full name: Snippet.cons
static member List.Cons : head:'T * tail:'T list -> 'T list
val parts : 'a list -> 'a list list list

Full name: Snippet.parts
val x' : 'a
val glue : 'a -> 'a list list -> 'a list list

Full name: Snippet.glue
val xss : 'a list list

type: 'a list list
implements: System.Collections.IStructuralEquatable
implements: System.IComparable<List<'a list>>
implements: System.IComparable
implements: System.Collections.IStructuralComparable
implements: System.Collections.Generic.IEnumerable<'a list>
implements: System.Collections.IEnumerable
val head : 'T list -> 'T