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?
A recursive lambda expression is the process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily.
This is an example of a function that will recursively call itself. Warning It's possible to run into infinite loops with recursive calls. Test your functions locally before deploying to production.
Recursion is important to Haskell because unlike imperative languages, you do computations in Haskell by declaring what something is instead of declaring how you get it. That's why there are no while loops or for loops in Haskell and instead we many times have to use recursion to declare what something is.
The principle of tail recursion is to perform all computation first before the recursive call, often giving the results of the computation as additional argument to the recursively called function. Thus in tail recursion the recursive call is the last logic instruction in the recursive function.
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!)
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
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With