Return to Answer

You need the following combinators, which are in the standard library. I have also given their standard names from combinator calculus.

id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

Work with one parameter at a time. Move parameters on the left to lambdas on the right, e.g.

f x y = Z

becomes

f = \x -> \y -> Z

I like to do this one argument at a time rather than all at once, it just looks cleaner.

Then eliminate the lambda you just created according to the following rules. I will use lowercase letters for literal variables, uppercase letters to denote more complex expressions.

1. If you have \x -> x, replace with id
2. If you have \x -> A, where A is any expression in which x does not occur, replace with const A
3. If you have \x -> A x, where x does not occur in A, replace with A. This is known as "eta contraction".
4. If you have \x -> A B, then
5. If x occurs in both A and B, replace with (\x -> A) <*> (\x -> B).
6. If x occurs in just A, replace with flip (\x -> A) B
7. If x occurs in just B, replace with A . (\x -> B),
8. If x does not occur in either A or B, well, there's another rule we should have used already.

And then work inward, eliminating the lambdas that you created.

You need the following combinators, which are in the standard library. I have also given their standard names from combinator calculus.

id :: a -> a                                   -- I
const :: a -> b -> a                           -- K
(.) :: (b -> c) -> (a -> b) -> (a -> c)        -- B
flip :: (a -> b -> c) -> (b -> a -> c)         -- C
(<*>) :: (a -> b -> c) -> (a -> b) -> (a -> c) -- S

Work with one parameter at a time. Move parameters on the left to lambdas on the right, e.g.

f x y = Z

becomes

f = \x -> \y -> Z

I like to do this one argument at a time rather than all at once, it just looks cleaner.

Then eliminate the lambda you just created according to the following rules. I will use lowercase letters for literal variables, uppercase letters to denote more complex expressions.

1. If you have \x -> x, replace with id
2. If you have \x -> A, where A is any expression in which x does not occur, replace with const A
3. If you have \x -> A x, where x does not occur in A, replace with A. This is known as "eta contraction".
4. If you have \x -> A B, then
5. If x occurs in both A and B, replace with (\x -> A) <*> (\x -> B).
6. If x occurs in just A, replace with flip (\x -> A) B
7. If x occurs in just B, replace with A . (\x -> B),
8. If x does not occur in either A or B, well, there's another rule we should have used already.

And then work inward, eliminating the lambdas that you created.

5. If you have A B x, where x does not occur in A, replace with (\x -> B) >>= A.

5. If you have \x -> A B x, where x does not occur in A, replace with (\x -> B) >>= A.

Sometimes a shortcut with >>= is possible:

5. If you have A B x, where x does not occur in A, replace with (\x -> B) >>= A.