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
Raw view Test code New version

More information

Link:http://fssnip.net/m0
Posted:10 years ago
Author:Dmitri Soshnikov
Tags: factorial , combinators , learning

This web site is created using F# and Suave web server. It is hosted on Azure and the source code is on GitHub. Contributions are welcome!

The first version of fssnip.net has been created by @tomaspetricek back in 2010. This web site is a new, open-source and contribution-friendly version.