1

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?

Improve this question
1
  • Note the lambda itself is not recursive; it just takes a function which it applies to n - 1. Commented Mar 5, 2016 at 20:49

3 Answers 3

Reset to default
5

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
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Ok, I have a doubt with that: t(n-1). t is our lambda function. t ( lambda) gets TWO arguments while we give one argument ( n -1). My guess is that is connected with laziness of Haskell? Can you explain me it in more details? If you suggest, I'll create a new subject,
no t has only one argument and if you look closely we only call it ever with one - the lambda part is the \ t n -> ... - see this (unnamed) function takes two arguments: one is t and the other is n - this is the tricky mind-bending part as this enables us to define recursive with only the y-fix point combinator
It it is caused by the fact that the recursion will be infinitely ( to stop constraint) expanded and there is no 'place for t argument'. Am I right?
I am not sure I understand what you are trying to say - the recursion here will stop because you finally hit the then branch where you don't use t again (the part where y brings in the recursive call into the computation) - although I talked about laziness at first it's not really needed here as if will evaluate only one branch in most lang. I know (in ML/F#, etc. it will work as is) and I decided it might confuse to much here
Thanks you very much for your help and patience! :)
1

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.