Y combinator: Difference between revisions
(The second task starting with a Y!) |
(added haskell) |
||
| Line 2: | Line 2: | ||
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 would rule out the more 'normal' definition of a recursive function where a function is associated with the state of a variable and this variables state is used in the body of the function. |
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 would rule out the more 'normal' definition of a recursive function where a function is associated with the state of a variable and this variables 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 [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]]. |
||
The task is to define the stateless Y combinator and use it to compute [[wp:Factorial|factorials]] and [[wp: |
The task is to 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. |
||
Note: The Python example shows one way to complete the task. |
Note: The Python example shows one way to complete the task. |
||
=={{header|Haskell}}== |
|||
<lang haskell>y f = f (y f) |
|||
fac f 0 = 1 |
|||
fac f x = x * f (x-1) |
|||
fib f 0 = 0 |
|||
fib f 1 = 1 |
|||
fib f x = f (x-1) + f (x-2) |
|||
main = do print [ y fac i | i <- [0..9] ] |
|||
print [ y fib i | i <- [0..9] ]</lang> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
Revision as of 08:02, 28 February 2009
You are encouraged to solve this task according to the task description, using any language you may know.
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 would rule out the more 'normal' definition of a recursive function where a function is associated with the state of a variable and this variables 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.
The task is to define the stateless Y combinator and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.
Note: The Python example shows one way to complete the task.
Haskell
<lang haskell>y f = f (y f)
fac f 0 = 1 fac f x = x * f (x-1)
fib f 0 = 0 fib f 1 = 1 fib f x = f (x-1) + f (x-2)
main = do print [ y fac i | i <- [0..9] ]
print [ y fib i | i <- [0..9] ]</lang>
Python
<lang python>>>> Y = lambda f: (lambda x: x(x))(lambda y: f(lambda z: y(y)(z))) >>> fac = lambda f: lambda n: (1 if n<2 else n*f(n-1)) >>> [ Y(fac)(i) for i in range(10) ] [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880] >>> fib = lambda f: lambda n: 0 if n == 0 else (1 if n == 1 else f(n-1) + f(n-2)) >>> [ Y(fib)(i) for i in range(10) ] [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]</lang>