1 people like it.
Like the snippet!
Stepbystep explanation of the Y combinator
Describes a function called "fix" that can be used to generate recursive functions from nonrecursive functions, with some simple examples. (Updated with slightly improved comments.)
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:

/// For a function, f, define fix(f) as the "fixed point" of f:
/// A value, z, such that f(z) = z.
///
/// Substituting fix(f) for z, gives f(fix(f)) = fix(f), which
/// we flip to fix(f) = f(fix(f)).
///
/// This fixed point, z, is itself a function that takes an
/// argument, x. We have to make x explicit in the definition
/// in order to avoid infinite recursion when fix is called.
///
/// (In a typed language like F#, fix has to be defined recursively.
/// However, in an untyped system, such as the pure lambda calculus,
/// fix can be defined without recursion. That version of fix is
/// called the "Y" combinator.)
///
/// https://en.wikipedia.org/wiki/Fixedpoint_combinator
let rec fix f =
let z x = (f (fix f)) x
z
/// As an example, we create a factorial "generator", which, when
/// given a function that implements factorial correctly for inputs
/// up to some number, n1, answers a slightly better function that
/// implements factorial correctly for n as well. Note that this
/// function is not recursive.
let factorialGen (factorialWeak : int > int) : (int > int) =
fun n >
if n = 0 then 1
else n * factorialWeak (n  1)
/// We could feed such a generated function back into the generator
/// to produce an even better version that works for all numbers
/// up to n + 1. Instead, applying fix to the generator itself
/// returns the generator's fixed point, as though we had iterated
/// the feedback infinitely. The result is a function that implements
/// factorial correctly for *all* inputs n.
let factorial = fix factorialGen
/// Another example: Fibonacci numbers. Again, fibGen itself isn't
/// recursive. It only behaves recursively once we apply fix.
let fib =
let fibGen fibWeak =
fun n >
if n <= 1 then 1
else fibWeak (n  1) + fibWeak (n  2)
fix fibGen
[<EntryPoint>]
let main argv =
printfn ""
for i = 0 to 10 do
printfn "%A!: %A" i (factorial i)
printfn ""
for i = 0 to 10 do
printfn "fib(%A): %A" i (fib i)
0

val fix : f:(('a > 'b) > 'a > 'b) > ('a > 'b)
Full name: Script.fix
For a function, f, define fix(f) as the "fixed point" of f:
A value, z, such that f(z) = z.
Substituting fix(f) for z, gives f(fix(f)) = fix(f), which
we flip to fix(f) = f(fix(f)).
This fixed point, z, is itself a function that takes an
argument, x. We have to make x explicit in the definition
in order to avoid infinite recursion when fix is called.
(In a typed language like F#, fix has to be defined recursively.
However, in an untyped system, such as the pure lambda calculus,
fix can be defined without recursion. That version of fix is
called the "Y" combinator.)
https://en.wikipedia.org/wiki/Fixedpoint_combinator
val f : (('a > 'b) > 'a > 'b)
val z : ('a > 'b)
val x : 'a
val factorialGen : factorialWeak:(int > int) > n:int > int
Full name: Script.factorialGen
As an example, we create a factorial "generator", which, when
given a function that implements factorial correctly for inputs
up to some number, n1, answers a slightly better function that
implements factorial correctly for n as well. Note that this
function is not recursive.
val factorialWeak : (int > int)
Multiple items
val int : value:'T > int (requires member op_Explicit)
Full name: Microsoft.FSharp.Core.Operators.int

type int = int32
Full name: Microsoft.FSharp.Core.int

type int<'Measure> = int
Full name: Microsoft.FSharp.Core.int<_>
val n : int
val factorial : (int > int)
Full name: Script.factorial
We could feed such a generated function back into the generator
to produce an even better version that works for all numbers
up to n + 1. Instead, applying fix to the generator itself
returns the generator's fixed point, as though we had iterated
the feedback infinitely. The result is a function that implements
factorial correctly for *all* inputs n.
val fib : (int > int)
Full name: Script.fib
Another example: Fibonacci numbers. Again, fibGen itself isn't
recursive. It only behaves recursively once we apply fix.
val fibGen : ((int > int) > int > int)
val fibWeak : (int > int)
Multiple items
type EntryPointAttribute =
inherit Attribute
new : unit > EntryPointAttribute
Full name: Microsoft.FSharp.Core.EntryPointAttribute

new : unit > EntryPointAttribute
val main : argv:string [] > int
Full name: Script.main
val argv : string []
val printfn : format:Printf.TextWriterFormat<'T> > 'T
Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val i : int
More information