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

[<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/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

More information

Link:http://fssnip.net/7W9
Posted:4 years ago
Author:Brian Berns
Tags: fixed point , fixed-point , fixed-point combinator , fixedpoint , lambda calculus , recursion , recursive , y combinator , y-combinator