Marty Stumpf

7 Apr 2022

•

5 min read

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!

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

`λ`

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
```

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.

`map`

function: applying a function over a listHere 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!

Did you like this article?

Marty Stumpf

Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

See other articles by Marty

hello@works-hub.com

Ground Floor, Verse Building, 18 Brunswick Place, London, N1 6DZ

108 E 16th Street, New York, NY 10003

Join over 111,000 others and get access to exclusive content, job opportunities and more!