Haskell - Lambda calculus equivalent syntax?

Question

While writing some lambda functions in Haskell, I was originally writing the functions like:

tru = \t f -> t
fls = \t f -> f

However, I soon noticed from the examples online that such functions are frequently written like:

tru = \t -> \f -> t
fls = \t -> \f -> f

Specifically, each of the items passed to the function have their own \ and -> as opposed to above. When checking the types of these they appear to be the same. My question is, are they equivalent or do they actually differ in some way? And not only for these two functions, but does it make a difference for functions in general? Thank you much!

Answer 1

They're the same, Haskell automatically curries things to keep things syntax nice. The following are all equivalent**

foo a b = (a, b)
foo a = \b -> (a, b)
foo = \a b -> (a, b)
foo = \a -> \b -> (a, b)
-- Or we can simply eta convert leaving
foo = (,)

If you want to be idiomatic, prefer either the first or the last. Introducing unnecessary lambdas is good for teaching currying, but in real code just adds syntactic clutter.

However in raw lambda calculus (not Haskell) most manually curry with

\a -> \b -> a b

Because people don't write a lot of lambda calculus by hand and when they do they tend to stick unsugared lambda calculus to keep things simple.

** modulo the monomorphism restriction, which won't impact you anyways with a type signature.

Answer 2

Though, as jozefg said, they are themselves equivalent, they may lead to different execution behaviour when combined with local variable bindings. Consider

f, f' :: Int -> Int -> Int

with the two definitions

f a x = μ*x
 where μ = sum [1..a]

and

f' a = \x -> μ*x
 where μ = sum [1..a]

These sure look equivalent, and certainly will always yield the same results.

GHCi, version 7.6.2: http://www.haskell.org/ghc/ :? for help
...
[1 of 1] Compiling Main            ( def0.hs, interpreted )
Ok, modules loaded: Main.
*Main> sum $ map (f 10000) [1..10000]
2500500025000000
*Main> sum $ map (f' 10000) [1..10000]
2500500025000000

However, if you try this yourself, you'll notice that with f takes quite a lot of time whereas with f' you get the result immediately. The reason is that f' is written in a form that prompts GHC to compile it so that actually f' 10000 is evaluated before starting to map it over the list. In that step, the value μ is calculated and stored in the closure of (f' 10000). On the other hand, f is treated simply as "one function of two variables"; (f 10000) is merely stored as a closure containing the parameter 10000 and μ is not calculated at all at first. Only when map applies (f 10000) to each element in the list, the whole sum [1..a] is calculated, which takes some time for each element in [1..10000]. With f', this was not necessary because μ was pre-calculated.

In principle, common-subexpression elimination is an optimisation that GHC is able to do itself, so you might at times get good performance even with a definition like f. But you can't really count on it.