How to write recursive lambda expression in Haskel

问题:

I am not sure if this is good programming practice, but I would like to know if one can define a recursive function using the lambda expression.

This is an artificial example I made up: So one can defined the factorial function in Haskell recursively as follows

factorial :: Integer -> Integer 
factorial 1 = 1
factorial (n + 1) = (n + 1) * factorial n

Now, I want a function f such that f n = (factorial n) + 1. Rather than using a name for factorial n (i.e. defining it before hand), I want to define f where factorial n is given a lambda expression within the definition of f. Can I use a recursive lambda definition in f in place of using the name factorial?

回答1:

The canonical way to do recursion with pure lambda expressions is to use a fixpoint combinator, which is a function with the property

fixpoint f x = f (fixpoint f) x

If we assume that such a combinator exists, we can write the recursive function as

factorial = fixpoint (\ff n -> if n == 1 then 1 else n * ff(n-1))

The only problem is that fixpoint itself is still recursive. In the pure lambda calculus, there are ways to create fixpoint combinators that consist only of lambdas, for example the classical "Y combinator":

fixpoint f = (\x -> f (x x)) (\x -> f (x x))

But we still have problems, because this definition is not well-typed according to Haskell -- and it can be proved that there is no way to write a well-typed fixpoint combinator using only lambdas and function applications. It can be done by use of an auxiliary data type to shoehorn in some type recursion:

data Paradox a = Self (Paradox a -> a)
fixpoint f = let half (Self twin) = f (twin (Self twin))
             in half (Self half)

(Note that if the injections and projections from the singleton data type are removed, this is exactly the Y combinator!)

回答2:

Yes, using the fixed-point function fix:

fact :: Int -> Int
fact = fix (\f n -> if n == 0 then 1 else n * (f (n-1)))

Basically, it doesn't have a name, since it's a lambda expression, so you take the function in as an argument. Fix applies the function to itself "infinitely" many times:

fix f = f (fix f)

and is defined in Data.Function.

回答3:

Why do we use lambda's instead of let in?

Prelude> (let fib n = if n == 1 then 1 else n * fib(n-1) in fib ) 4
24

回答4:

Owen is spot on with the fix function

Prelude> fix f = f (fix f)
Prelude> fix (\f n -> if n == 0 then 1 else n * f (n - 1)) 6
720

The nameless Lambda function is self terminating even if fix is not. Owen's fix function beats the fix function typically used in Haskell which is

fix :: (a -> a) -> a
fix f = let {x = f x} in x

Both allow anonymous recursive lambda functions