Curry for Breakfast
Haskell is closely based on the lambda calculus. This is especially interesting in the context of functions that take multiple arguments. Consider this toy function:
Prelude> let func a b = a + b
What would you expect its type to be? If you come from an Algol-family language, then you'd probably expect it to be something that takes two numbers and returns one number. Let's see what ghc says:
Prelude> :type func func :: Num a => a -> a -> a
In fact, it's a function that takes a number and returns a function that takes another number. You can see this by calling it with just one argument:
Prelude> let addFive = func 5 Prelude> :type addFive addFive :: Integer -> Integer Prelude> addFive 12 17
Calling this function with just one argument gave us a new function that took just one argument and added 5 to it. Note also that this refined the type slightly. Because 5 is an integer (not just a number) and the operands of the + expression must be the same, the addFive function will work only on integers, while func will also work on floating point values.
In fact, functions in Haskell are just names for lambda expressions. In Lambda calculus, you would write func as λxy.x+y and addFive as λy.5+y. You can also use this syntax in Haskell, although since most keyboards don't include a λ symbol, Haskell uses a \ instead. These become:
\x y -> x + y \y -> 5 + y
This is one of the most interesting things about Haskell from a compiler perspective, because it means that you can easily create partial specializations of functions. It's also interesting for programmers because it lets you break down problems at a fairly arbitrary granularity.
Higher Order Functions
Because functions are just names for lambda expressions, you can use them anywhere where you can use any other value. Operations like map and zip are defined in exactly the converse of the way that we just saw. Rather than being functions that return functions, they are functions that take functions as arguments.
As with other Haskell functions, higher order functions can be generic. Consider the map function:
Prelude> :type map map :: (a -> b) -> [a] -> [b]
This takes a function that maps from type a to type b and returns a function that takes lists with elements of type a and returns a list with elements of type b. You can call this with just a function and get a specialized form of map, for example:
Prelude> :type map (\x -> x + 1) map (\x -> x + 1) :: Num b => [b] -> [b]
This gives a new function that takes a list of numbers and returns a list of numbers. You can either call this function once or give it a name and call it multiple times:
Prelude> map (\x -> x + 1) [1, 2, 3] [2,3,4] Prelude> let incList = map (\x -> x + 1) Prelude> incList [1, 2, 3, 4, 5] [2,3,4,5,6] Prelude> incList  
This is another place where it's potentially interesting for compiler developers. Whether it's worth generating code for a specialized version of map instead of calling a generic one and calling the function passed as an argument can make a big difference to performance.