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: // 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 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
  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

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

val tail : 'T list -> 'T list

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

val choices : 'a list -> 'a list list

Full name: Snippet.choices

More information

Link:	http://fssnip.net/48
Posted:	2 years ago
Author:	Cesar Mendoza (website)
Tags:	Combinatorial functions, mathematics, recursion, Permutations, Combinatorial