Newbie: Recursive lambda definitions?

Submitted by dokondr on Sat, 03/18/2006 - 1:04pm.

{-
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?
-}

Submitted by leemarks on Sat, 03/18/2006 - 5:11pm.

Anonymous recursive functions are possible if you have a Y-combinator defined:

y f = f (y f)

Using this your total function above can be translated quite directly as

total f = y (\tot n -> if n >= 0 then f n + tot (n - 1) else 0)

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

total f n = sum [f i | i <- [0..n]]

or equivalently in point-free form

total f = sum . map f . enumFromTo 0
Submitted by dokondr on Tue, 03/21/2006 - 3:53am.

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!

Submitted by Pseudonym on Sat, 03/18/2006 - 5:19pm.

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)
fix function is recursive, but in some sense it abstracts all recursion.

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!).

Submitted by dokondr on Tue, 03/21/2006 - 4:17am.

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?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.