In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions.

This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function.

The   Y combinator   is itself a stateless function that, when applied to another stateless function, returns a recursive version of the function.

The Y combinator is the simplest of the class of such functions, called fixed-point combinators.



Task

Define the stateless   Y combinator   and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.



Cf

 Jim Weirich: Adventures in Functional Programming


# 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(), " "
echo()