Y combinator: Difference between revisions

=={{header|Nim}}==

<lang nim># The following is implemented for a strict language as a Z-Combinator;

# Z-combinators differ from Y-combinators in lacking one Beta reduction of

# the extra `T` argument to the function to be recursed...

import sugar

proc fixz[T, TResult](f: ((T) -> TResult) -> ((T) -> TResult)): (T) -> TResult =

type RecursiveFunc = object # any entity that wraps the recursion!

recfnc: ((RecursiveFunc) -> ((T) -> TResult))

let g = (x: RecursiveFunc) => f ((a: T) => x.recfnc(x)(a))

g(RecursiveFunc(recfnc: g))

let facz = fixz((f: (int) -> int) =>

((n: int) => (if n <= 1: 1 else: n * f(n - 1))))

let fibz = fixz((f: (int) -> int) =>

((n: int) => (if n < 2: n else: f(n - 2) + f(n - 1))))

echo facz(10)

echo fibz(10)

# by adding some laziness, we can get a true Y-Combinator...

# note that there is no specified parmater(s) - truly fix point!...

#[

proc fixy[T](f: () -> T -> T): T =

type RecursiveFunc = object # any entity that wraps the recursion!

recfnc: ((RecursiveFunc) -> T)

let g = ((x: RecursiveFunc) => f(() => x.recfnc(x)))

g(RecursiveFunc(recfnc: g))

# ]#

# same thing using direct recursion as Nim has...

# note that this version of fix uses function recursion in its own definition;

# thus its use just means that the recursion has been "pulled" into the "fix" function,

# instead of the function that uses it...

proc fixy[T](f: () -> T -> T): T = f(() => (fixy(f)))

# these are dreadfully inefficient as they becursively build stack!...

let facy = fixy((f: () -> (int -> int)) =>

((n: int) => (if n <= 1: 1 else: n * f()(n - 1))))

let fiby = fixy((f: () -> (int -> int)) =>

((n: int) => (if n < 2: n else: f()(n - 2) + f()(n - 1))))

echo facy 10

echo fiby 10

# something that can be done with the Y-Combinator that con't be done with the Z...

# given the following Co-Inductive Stream (CIS) definition...

type CIS[T] = object

head: T

tail: () -> CIS[T]

# Using a double Y-Combinator recursion...

# defines a continuous stream of Fibonacci numbers; there are other simpler ways,

# this way implements recursion by using the Y-combinator, although it is

# much slower than other ways due to the many additional function calls,

# it demonstrates something that can't be done with the Z-combinator...

iterator fibsy: int {.closure.} = # two recursions...

let fbsfnc: (CIS[(int, int)] -> CIS[(int, int)]) = # first one...

fixy((fnc: () -> (CIS[(int,int)] -> CIS[(int,int)])) =>

((cis: CIS[(int,int)]) => (

let (f,s) = cis.head;

CIS[(int,int)](head: (s, f + s), tail: () => fnc()(cis.tail())))))

var fbsgen: CIS[(int, int)] = # second recursion

fixy((cis: () -> CIS[(int,int)]) => # cis is a lazy thunk used directly below!

fbsfnc(CIS[(int,int)](head: (1,0), tail: cis)))

while true: yield fbsgen.head[0]; fbsgen = fbsgen.tail()

let fibs = fibsy

for _ in 1 .. 20: stdout.write fibs(), " "</lang>

{{out}}

<pre>3628800

55

3628800

55

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181</pre>

At least this last example version building a sequence of Fibonacci numbers doesn't build stack as it the use of CIS's means that it is a type of continuation passing/trampolining style.

Note that these would likely never be practically used in Nim as the language offers both direct variable binding recursion and recursion on proc's as well as other forms of recursion so it would never normally be necessary. Also note that these implementations not using recursive bindings on variables are "non-sharing" fix point combinators, whereas sharing is sometimes desired/required and thus recursion on variable bindings is required.