## Haskell: 10 characters

```
y f=f$y f
```

Example of use to create recursive definitions of factorial or nth-Fibonacci:

```
> map ( y(\f n->if n <= 1 then 1 else n*f(n-1)) ) [1..10]
[1,2,6,24,120,720,5040,40320,362880,3628800]
> map ( y(\f n->if n <= 1 then 1 else f(n-1)+f(n-2)) ) [0..10]
[1,1,2,3,5,8,13,21,34,55,89]
```

Though, a more common way to use `y`

would be to generate these sequences directly, rather than as functions:

```
> take 10 $ y(\p->1:zipWith (*) [2..] p)
[1,2,6,24,120,720,5040,40320,362880,3628800]
> take 11 $ y(\f->1:1:zipWith (+) f (tail f))
[1,1,2,3,5,8,13,21,34,55,89]
```

Of course, with Haskell, this is a bit like shooting fish in a barrel! The `Data.Function`

library has this function, called `fix`

, though implemented somewhat more verbosely.

Is a lazy-language implementation ok? (Would you accept

`(define Y(lambda(f)(f(Y f))))`

?) – Eelvex – 2011-02-19T20:28:44.843Any implementation you can demonstrate with one of the requested examples is ok. – J B – 2011-02-19T21:52:40.547

1If I'm not mistaken, strictly speaking, the term "Y combinator" refers specifically to a single fixpoint combinator discovered by Haskell Curry, λf.(λx.f (x x)) (λx.f (x x)) . – Joey Adams – 2011-02-20T01:32:49.400

@Eelvex: Obviously both answers so far (including the OP's own answer) use the cheating way, so, I guess that makes it okay. :-P Personally, I'd rather go with @Joey's approach and say that only the real (non-self-referential) Y combinator will do. ;-) – Chris Jester-Young – 2011-02-20T02:21:09.093

@Chris: Oh my. That's what I had in mind initially, and then I... forgot along the way. It's kind of too late to change now, we'll have to open another question. – J B – 2011-02-20T11:06:52.487