 6 people like it.

# Step-by-step explanation of the Y combinator

Describes a function called "fix" that can be used to generate recursive functions from non-recursive 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/Fixed-point_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, n-1, 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 [] 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/Fixed-point_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, n-1, 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