How to write recursive lambda expression in Haskell?

Question

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?

Why not just give it a name? It doesn't have to be a global name, there's let and where. — user395760
– user395760, Commented Aug 21, 2011 at 21:20
As an aside, note that n+k patterns as used in your definition of factorial have been removed from the language as of Haskell 2010. It's advisable to stop using them. — hammar
– hammar, Commented Aug 21, 2011 at 21:58
p.s. I prefer the base case 0: factorial 0 = 1 which will allow it to work for one more number — newacct
– newacct, Commented Aug 22, 2011 at 0:41
@delnan: I guess you wont like my code since almost all of it imports Data.Function (fix) — L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳
– L̲̳o̲̳̳n̲̳̳g̲̳̳p̲̳o̲̳̳k̲̳̳e̲̳̳, Commented Mar 29, 2013 at 6:22

John L · Accepted Answer · 2011-08-22 14:25:27Z

32

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

edited Aug 22, 2011 at 14:25

John L

28.1k4 gold badges76 silver badges89 bronze badges

answered Aug 21, 2011 at 21:21

hmakholm left over Monica

23.4k3 gold badges55 silver badges75 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Rotsor Over a year ago

Although it does not typecheck, one can still have fun with it! factorial, factorial 3 :)

dfeuer Over a year ago

Is there a reason to use data here, or will newtype work as well (better)?

hmakholm left over Monica Over a year ago

@dfeuer: Probably newtype would work better -- I wasn't aware of that language feature when I wrote the answer.

Owen · Accepted Answer · 2014-06-02 16:30:59Z

32

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.

edited Jun 2, 2014 at 16:30

answered Aug 21, 2011 at 21:19

Owen

39.5k14 gold badges98 silver badges131 bronze badges

Comments

Anon Imous · Accepted Answer · 2015-06-21 23:12:53Z

1

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

answered Jun 21, 2015 at 23:12

Anon Imous

4152 silver badges12 bronze badges

1 Comment

ThreeFx Over a year ago

let still requires naming functions.

fp_mora · Accepted Answer · 2018-02-15 02:31:40Z

0

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

edited Feb 15, 2018 at 2:31

answered Feb 15, 2018 at 0:06

fp_mora

7246 silver badges11 bronze badges

Collectives™ on Stack Overflow

How to write recursive lambda expression in Haskell?

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related