Let's say I want to define a function:

This function multiplies an input by two, adds one to this integer, then divides it by two in that order.

f represents the multiplication, g represents the addition, and h represents the division.

Could I represent this as λx.fxgh, when explicitly defined with parentheses is shown as λx.(((fx)g)h))?

I would think that is correct, because you evaluate the innermost function first, then move outwards treating each evaluated function on the inside as input for the next one, no?


It's valid (because it respects $\lambda$-calculus syntax) but won't work as you expect. To see that just take your favorite language and try it out:

let f = \x -> 2*x
let g = \y -> y+1
let h = \z -> z/2

(\x -> (((fx)g)h))) 1 won't evaluate to $1.5$. Why?

Because $g$ and $h$ are functions and take one argument each, and application happens when there's an abstraction to the left. So if you change the order you will get the expected behavior.

$$ \lambda x. (h (g (f ~ x))) $$


$$ \lambda x. ((h \circ g \circ f) ~ x) $$

In Haskell:

(\x -> (h . g . f) x)

where . ($\circ$) is for function composition.


$$ \big(\lambda x. (h (g (f ~ x)))\big) 1 \rightarrow (h (g (f ~ 1))) \rightarrow (h (g ~ 2)) \rightarrow (h ~ 3) \rightarrow 1.5 $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.