5 people like it.

# 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: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: ``` ``````// 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 // this function is also know as the powerset. 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]]] // This one comes from the book "Programming in Haskell" by Graham Hutton. // The function choices returns all the way you can select elements from a list let choices xs = List.concat (List.map perms (subs xs)) // > choices [1..3];; // val it : int list list = // [[]; [1]; [2]; [1; 2]; [2; 1]; [3]; [1; 3]; [3; 1]; [2; 3]; [3; 2]; // [1; 2; 3]; [2; 1; 3]; [2; 3; 1]; [1; 3; 2]; [3; 1; 2]; [3; 2; 1]] ``````
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 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