CODEWITHSUNDEEP
haskelllambda
Gilgamesz
Gilgamesz

Reputation: 5073

Recursive lambda in Haskell

Let's see analyse code for factorial in Haskell using lambda function:

y f x = f (y f) x

factorial = y (\t n -> if n == 1 then 1 else n * t(n-1))

And I cannot understand how does it works. I know that it is connected with lambda calculus but nowadays I am not familiar with that so I have to understand without it or with minimal knowledge. My doubt is: What is f in definition of factorial? I mean this f: y f x = f (y f) x.

So what is f here? y (\t n -> if n == 1 then 1 else n * t(n-1))

Please explain me that, maybe expand recursion?

Upvotes: 1

Views: 1373

Answers (3)

Random Dev
Random Dev

Reputation: 52300

the fin factorial is the (\t n -> if n == 1 ...) lambda

y is a so called fix-point combinator and it's used to enable recursive definitions in the lambda-calculus (it applies f to it's argument again and again recursively)

to understand how it works you can just do some evaluation by hand:

factorial 3
= y (\t n -> ...) 3
{ def y and y (\t n -> ...) = factorial by eta-red. }
= (\t n -> ...) factorial 3
{ t = factorial, n = 3 -> else case }
= 3 * factorial 2
= 3 * (y (\t n -> ...) 2)
= 3 * ((\t n -> ...) factorial 2)
= { t = factorial, n = 2 -> else case }
= 3 * (2 * factorial 1)
= 3 * (2 * (y (\t n -> ...) 1))
= 3 * (2 * ((\t n -> ...) factorial 1)))
{ t = factorial n = 1 -> then case }
= 3 * (2 * 1)
= 6

Upvotes: 5

leftaroundabout
leftaroundabout

Reputation: 120751

Perhaps it's easier if you write out the y combinator thus, with two eta-expansions:

y :: ((a->b) -> a->b) -> a->b
y f x a = f (\q a' -> y f q a') x a

So f basically gets the recursive call (with a' in place of a) as its first argument.

Upvotes: 0

Lee
Lee

Reputation: 144206

y is the fixed-point combinator, also known as the y-combinator. In

factorial = y (\t n -> if n == 1 then 1 else n * t(n-1))

the lambda (\t n -> if n == 1 then 1 else n * t(n-1)) is bound to f in the definition of y. You can then do the expansion:

(\t n -> if n == 1 then 1 else n * t(n-1)) (y (\t n -> if n == 1 then 1 else n * t(n-1)))

so inside the lambda, t will be bound to the lambda itself, which allows it to call itself recursively.

Upvotes: 1

Related Questions