patternMinor
Is this lambda abstraction created as a generator of a recursive function?
Viewed 0 times
thiscreatedabstractionfunctiongeneratorrecursivelambda
Problem
In lambda calculus, a recursive function $f$ is obtained by
$$ f = Y g $$
where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e. $f == g f$.
In The Scheme Programming Language, I saw an example implementing a recursive function $f$ that sums the integers in a list:
What is the mathematical derivation that drives to create the lambda abstraction
?
It looks like a generator of $f$, but not entirely.
Thanks.
$$ f = Y g $$
where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e. $f == g f$.
In The Scheme Programming Language, I saw an example implementing a recursive function $f$ that sums the integers in a list:
(let ([sum (lambda (f ls)
(if (null? ls)
0
(+ (car ls) (f f (cdr ls)))))])
(sum sum '(1 2 3 4 5))) => 15What is the mathematical derivation that drives to create the lambda abstraction
lambda (f ls)
(if (null? ls)
0
(+ (car ls) (f f (cdr ls))))?
It looks like a generator of $f$, but not entirely.
Thanks.
Solution
If you look at the $Z$ combinator (because we're in an eager context), you have $$Z=\lambda g.(\lambda f.g(\lambda v.ffv))(\lambda f.g(\lambda v.ffv))$$
If you look at the code, we don't apply a fixed point combinator to
You can also readily show that
If you look at the code, we don't apply a fixed point combinator to
sum, we simply apply sum to itself, so there's no reason for sum to be "generator".You can also readily show that
sum is (modulo currying) equal to $\lambda f.g(\lambda v.ffv)$ for some $g$, basically by replacing (f f ...) with (h ...) where h is the argument to $g$ in the definition for sum (minus the outermost lambda).Context
StackExchange Computer Science Q#113177, answer score: 4
Revisions (0)
No revisions yet.