18 lines
1.0 KiB
Plaintext
18 lines
1.0 KiB
Plaintext
In strict [[wp:Functional programming|functional programming]] and the [[wp:lambda calculus|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 [http://mvanier.livejournal.com/2897.html 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 [[wp:Fixed-point combinator|fixed-point combinators]].
|
|
|
|
|
|
;Task:
|
|
Define the stateless ''Y combinator'' and use it to compute [[wp:Factorial|factorials]] and [[wp:Fibonacci number|Fibonacci numbers]] from other stateless functions or lambda expressions.
|
|
|
|
|
|
;Cf:
|
|
* [http://vimeo.com/45140590 Jim Weirich: Adventures in Functional Programming]
|
|
<br><br>
|
|
|