Higher Order Functions: Lambda calculus, Currying, Maps

This is the second of a series of articles that illustrates functional programming (FP) concepts to imperative programmers. As you go through these articles with code examples in Haskell (one of the most popular FP languages), you gain the grounding for picking up any FP languages quickly. Why should you care about FP? See this post.

In the last post, we learned that in FP, recursions are used in place of loops. In this post, we'll go through another important concept: higher order functions, which dramatically increase one's expressive power.

In functional languages, functions are first-class citizens. That is, function is an entity that supports all the operations generally available to other entities. For example, functions can be passed as an argument, returned from a function, and assigned to a variable.

Lambda calculus is a formal system for representing function abstractions and applications and more. We'll first go through some basic lambda calculus concepts/notations. Then I'll explain the concept of currying. Finally, we'll look at the map function which takes a function as an input. After these, you will master functions like a pro FPer!

Functions and the Lambda (λ) Notation

Lambda Calculus builds on the concept of functions. A function takes in input(s), processes the input(s) and returns an output. E.g., a function can take an input x, and output x+1. Or, a function can take inputs x and y, and output x+y. In lambda calculus, we write these functions as

λx.x+1

λx.λy.x+y

These are called anonymous functions (functions that are unnamed). An input is preceded by a λ and followed by a dot. The last dot is followed by the output of the function.

In Haskell, λ is represented by \. We can write the above anonymous functions in Haskell:

\x -> x + 1

\x y -> x + y

We evaluate a function in the usual manner. In terms of notation, we write the value(s) of the input(s) after we define the function. E.g., when x = 5 in the first function above, we write:

(λx.x+1) 5 = 5 + 1 = 6

Or, when x = 5 and y = 7 in the second function, we write:

(λx.λy.x+y) 5 7 = 5 + 7 = 12

In a Haskell REPL (GHCi) we can see this in action:

Prelude> (\x -> x + 1) 5
6
Prelude> (\x y -> x + y) 5 7
12

Currying and Partial applications

A function can have more than one input. In lambda calculus, each input is preceded by a λ symbol. Another way of thinking about more than one input is currying. Currying a function of two inputs turns that function into a function with one input by passing one of the inputs into it. In other words, currying turns f(x,y) to g(y) in which g is f with x passed into it. And g only takes one input, y. For example:

f(x,y) = x + y if x = 3 then f(3,y) = 3 + y

Similarly in lambda calculus:

λx.λy.(x+y) 3 y
= λy.(3+y) y

One can curry recursively, and turn a function of any number of input to a function of that number of input minus one. For example:

λx.λy.λz.(x+y+z) 3 4 5
= λy.λz.(3+y+z) 4 5
= λz.(3+4+z) 5
= (3+4+5)

It is important to keep in mind that some functional languages curry their functions by default. To illustrate, we can examine the type signature of this function in Haskell. We can ask GHCi for the type signature of this function using :t in GHCi:

Prelude> :t (\x y z -> x + y + z)
(\x y z -> x + y + z) :: Num a => a -> a -> a -> a

The first part of the signature Num a => specifies that type a is an instance of the Num (numeric) typeclass. This typeclass includes the integer type and the floating point number types. a has to be an instance of the numeric class because the operation + is an instance of this typeclass.

The function λx.λy.λz.(x+y+z) is a function with type signature a -> a -> a -> a. It takes an input of type a and returns a partially applied function λy.λz.(3+y+z) with type signature a -> a -> a. λy.λz.(3+y+z) takes an input of type a and returns another partially applied function λz.(3+4+z) with type signature a -> a. λz.(3+4+z) takes an input of type a and returns a type a.

Let’s look at an example of a higher ordered function. The function g checks whether a number is greater than 100 after it's been passed through a function:

Prelude> g f y = f y > 100
Prelude> g (\x -> x + 1) 20
False
Prelude> g (\x -> x + 1) 100
True

Let's look at it's type signature:

Prelude> :t g 
g :: (Ord a, Num a) => (t -> a) -> t -> Bool

The first input type is (t -> a). No currying is involved here. It is a function that takes one input of a generic type t, and returns an output of type a. Haskell treats g as a function that takes in f, and returns a function (with f passed in) that takes and passes in an input of type t. The output of g is a Bool. If f were to take more than one input, Haskell curries it:

Prelude> h f x y = f x y > 100
Prelude> :t h 
h
  :: (Ord a, Num a) => (t1 -> t2 -> a) -> t1 -> t2 -> Bool

Again, the first input is a function. f takes in 2 inputs x,y. Haskell curries it, similar to above.

The map function: applying a function over a list

Here I'm not talking about the map data structure, rather the function that applies a function over a list structure. It takes a function (with signature a -> b) as an input, and a list with elements of type a as the second input, and applies the function to every list element, turning each to type b. A list of elements of type b is returned:

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

For example, if we pass in our anonymous function (\x -> x + 1) to the list containing the numbers from 1 to 10 (in Haskell, the shorthand for it is [1..10]):

Prelude> map (\x -> x + 1) [1..10]
[2,3,4,5,6,7,8,9,10,11]

Note that we can pass in any function with the signature (a -> b). For example, the function of λx.λy.(x+y) when applied to only one argument returns a function of type a -> a, so it can be the first input of the map function:

Prelude> :t (\x y-> x + y) 10
(\x y-> x + y) 10 :: Num a => a -> a
Prelude> map ((\x y-> x + y) 10) [1..10]
[11,12,13,14,15,16,17,18,19,20]

Whew! We've gone through a few very important concepts! We've learned a bit of lambda calculus, typeclasses, currying, and the map function! This makes us ready for the super powerful recursion schemes that will be coming up in the next posts!

Enjoyed this blog? Sign up to Functional Works for more nuggets like these!