2 people like it.

# Computing factorial using combinators

This snippet shows how to transform simple recursive factorial function to combinator form step-by-step.

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: ``` ``````// First, let's define some combinators... let s f g x = f x (g x) let k x y = x let b f g x = f (g x) let c f g x = f x g let rec y f x = f (y f) x let cond p f g x = if p x then f x else g x // The following functions show the steps to transform // original definition of factorial into combinatorial form let rec fact0 n = if n=0 then 1 else n*fact0(n-1) let fact1 = y (fun f n -> if n=0 then 1 else n*f(n-1)) let fact2 = y (fun f -> cond ((=)0) (k 1) (s (*) (b f (c(-)1)))) let fact3 = y (b (cond ((=)0) (k 1)) (fun f->(s (*) (b f (c(-)1))))) // Final version let fact = y (b (cond ((=) 0) (k 1)) (b (s (*)) (c b (c(-)1)))) fact 5 ``````
val s : f:('a -> 'b -> 'c) -> g:('a -> 'b) -> x:'a -> 'c

Full name: Script.s
val f : ('a -> 'b -> 'c)
val g : ('a -> 'b)
val x : 'a
val k : x:'a -> y:'b -> 'a

Full name: Script.k
val y : 'b
val b : f:('a -> 'b) -> g:('c -> 'a) -> x:'c -> 'b

Full name: Script.b
val f : ('a -> 'b)
val g : ('c -> 'a)
val x : 'c
val c : f:('a -> 'b -> 'c) -> g:'b -> x:'a -> 'c

Full name: Script.c
val g : 'b
val y : f:(('a -> 'b) -> 'a -> 'b) -> x:'a -> 'b

Full name: Script.y
val f : (('a -> 'b) -> 'a -> 'b)
val cond : p:('a -> bool) -> f:('a -> 'b) -> g:('a -> 'b) -> x:'a -> 'b

Full name: Script.cond
val p : ('a -> bool)
val fact0 : n:int -> int

Full name: Script.fact0
val n : int
val fact1 : (int -> int)

Full name: Script.fact1
val f : (int -> int)
val fact2 : (int -> int)

Full name: Script.fact2
val fact3 : (int -> int)

Full name: Script.fact3
val fact : (int -> int)

Full name: Script.fact