We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to publish this job!

Login or register
to save this job!

Login or register
to save interesting jobs!

Login or register
to get access to all your job applications!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Login or register
to save articles!

Login to see the application

Engineers who find a new job through Functional Works average a 15% increase in salary 🚀

You will be redirected back to this page right after signin

Blog hero image

Higher Order Functions: Lambda calculus, Currying, Maps

Marty Stumpf 8 March, 2021 | 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!

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
Join our newsletter
Join over 111,000 others and get access to exclusive content, job opportunities and more!

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!

Author's avatar
Marty Stumpf
Software engineer. Loves FP Haskell Coq Agda PLT. Always learning. Prior: Economist. Vegan, WOC in solidarity with POC.

Related Issues

open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Started
  • 0
  • 1
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML
open-editions / corpus-joyce-ulysses-tei
open-editions / corpus-joyce-ulysses-tei
  • Open
  • 0
  • 0
  • Intermediate
  • HTML

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through Functional Works average a 15% increase in salary.

Start with GitHubStart with Stack OverflowStart with Email