Newbie: Recursive lambda definitions?
{-
Haskell newbie: Recursive lambda definitions?
Simon Thompson gives the following exercise (10.9) in his "Haskell. The Craft of Functional Programming" book:
10.9 Define a function total
total:: (Int -> Int) -> (Int -> Int)
so that total f is the function which at value n gives the total
f 0 + f 1 + ... + f n
I use 'where' clause to describe the resulting function 'tot':
-}
total:: (Int -> Int) -> (Int -> Int)
total f = tot
where
tot n
| n >= 0 = (f n) + (tot (n-1))
| otherwise = 0
test = total f1 4
{-
Q: Is it possible instead of naming and defining a resulting function (such as 'tot' in this example) just use recursive lambda definition? In this example recursion is required to create a function which is a variable sum of another function applications like:
f 0 + f 1 + ... + f n
Giving function a name ('tot' in this case) makes recursive definition possible. But what about lambda recursion? Can it be defined?
-}
- dokondr's blog
- Login to post comments
Anonymous recursive functions are possible if you have a Y-combinator defined:
Using this your total function above can be translated quite directly as
In practice however, it would be quite strange to write code like this in Haskell.
For your total function it would be easier to just say
or equivalently in point-free form
I still need to learn about Y-combinator :)
As for your example of using function composition - it definitely looks cleaner then my code.
Yet my goal was to find how an issue of anonymous recursive functions is addressed in Haskell, so that was the goal of my example question.
Thanks for your feedback. it really helps!
Congratulations! You've just discovered one of the central problems in early lambda calculus, and it's precisely this problem that resulted in types being introduced in the first place.
The short answer is that in general, you can't take a recursive function and turn it into a lambda expression.
Now here's the long answer.
You have a function:
> tot = ... tot ...
You can abstract out the recursive call by giving it a name:
> tot = (\r -> ... r ...) tot
What you have now is kind of like an equation to be solved. You have a lambda expression f and you want to find a lambda expression tot such that tot = f tot. In other words, you want to find a fixed point of f.
Sometimes, fixed points are expressible as lambda expressions, and sometimes they are not. The obvious fixed points of (\x -> x*x), which are 0 and 1, are expressible, for example.
However, in Haskell, there's a way to always find the "least" (in some technical sense) fixed point of a function:
fix :: (a -> a) -> a
fix f = let y = f y in y
Or slightly more clearly, though possibly less efficiently:
fix f = f (fix f)
In the case above, you can write your lambda expression as:
total f = fix (\tot n -> case n of
0 -> 0
_ -> f n + tot (n-1))
No recursion, except for the bit hidden inside fix.
Now reason why this was a problem in early lambda calculus was that it turns out that it's possible to express fix without recursion, if your language is untyped! Here it is:
-- Not valid Haskell. Try it and see.
fix = \f -> (\x -> f (x x)) (\x -> f (x x))
It turns out that the ability to express the fixed point operator is to lambda calculus what Russell's paradox is to set theory. The details aren't important, but it's for this reason that types were introduced (both to lambda calculus and to set theory!).
Thanks for the comments!
To illustrate my reasoning on the subject:
1)If something does not have a name then there is no way to call it.
2)Recursion function calls itself by defenition.
3)To call anybody, including itself, function must know the name of the party it calls.
4)Lambda function is anonymous function, does not have any name, so it can not call itself, so it can not be recursive.
5)Yet there could be some trick for lambda to refer to itself, some syntactic shugar like 'this' in OO languages.
Is this what you mean by "fixed point"?
To be frank I lost your reasoning at ths point:
>You can abstract out the recursive call by giving it a name:
> tot = (\r -> ... r ...) tot
What does this last notaion mean?