Newbie: Recursive lambda definitions?


Haskell newbie: Recursive lambda definitions?

10.9 Define a function total



f 0 + f 1 + ... + f n


total f = tot 
    tot n
	| otherwise = 0

test = total f1 4


f 0 + f 1 + ... + f n


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.

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:

What does this last notaion mean?

Comment viewing options
