Haskell series part 6

Thank you for joining us for the sixth part of our Haskell series, you will find the previous article here where I explain pattern matching and guards.

In this article we are going to cover higher order functions. It sounds like a big word, but this is something very natural that we are using without realizing it most of the time.

Definition

If a function does, either or both, of the following:

• Take a function as a parameter
• Return a function

Then it is a "higher order function", otherwise it is known as a "first order function".

A typical example of a higher order function is the map function:

Python 3.9.7 (default, Aug 31 2021, 13:28:12) 
>>> numbers = [1, 2, 3, 4, 5]
>>> list(map(lambda x: x * 2, numbers))
[2, 4, 6, 8, 10]

As you can see, we call the function map with 2 parameters:

• A lambda function (an anonymous function we do not need to define and usually write once - this concept can be found across almost all languages including Haskell) with a parameter x which is an element of the list numbers and returns the element time 2.
• The list of integers numbers.

Because map takes a function (lambda or not) as a parameter, it is therefore a higher order function.

Curried functions

Now for the big Haskell revelation: Every function in Haskell takes only 1 parameter.

This was a very confusing moment for me and probably for you right now, especially because we declared and used many functions in the previous articles which were using many parameters.

There is a technique that allows us to transform a function which takes many parameters into a function that returns one parameter which returns a function that returns one parameter and so on. This is called "currying", and luckily for us, all functions in Haskell are automatically curried.

Let's try to look at an example:

add :: Int -> Int -> Int
add a b = a + b

It is a simple function which takes two Int, adds them up and return the result, simple.

Let's load it and run it in  GHCI:

ghci> :l high-order.hs 
[1 of 1] Compiling Main             ( high-order.hs, interpreted )
Ok, one module loaded.
ghci> add 1 3
4

Works as expected.

What we do not see happening is actually the following:

• The parameter 1 is applied to our function add
• This will create a function on the fly which will take 1 parameter and add it to the number  1
• The parameter 3 is applied to our previous function
• Then 3 is added to 1 returning 4

Partial functions

Now, enough about the theoretical part, it is time to see how we can leverage this currying. In our previous example, when we broke down add 1 3, a function was created on the fly on step 2, this is called a partial function. We basically called the function without all its parameters.

Let's try again our add function:

ghci> let addThree = add 3
ghci> addThree 5
8

Nice, we are able to create the version of the function created on the fly on the step 2 and reuse it as we want.

Note that you need to "store" it using let,  which is an expression used to bind variables. You cannot not respect a function signature in Haskell:

ghci> add 3

<interactive>:7:1: error:
    • No instance for (Show (Int -> Int)) arising from a use of ‘print’
        (maybe you haven't applied a function to enough arguments?)
    • In a stmt of an interactive GHCi command: print it

Functions as a parameter

Now that we have a better understanding about how functions work under the hood with Haskell, let's try to create a higher order function. we are going to create a function which goes through a list and runs a function on every element of the list, then returns the new list (Sounds familiar ? map is reserved for the next article, we will get to it no worries).

add2 :: (Int -> Int) -> [Int] -> [Int]
add2 f list = [f x | x <- list]

So, let's break this down:

• We defined a new function called add2
• This function takes 2 parameters:
  1. (Int -> Int) : This is how you define a function that takes 1 integer and returns 1 integer. Do not mistake it for a tuple (Int, Int). Tuples uses , to separate their values, function definitions uses ->.
  2. [Int] : This is a list of integers
• And returns a value [Int] which is a list of integers

Now for the implementation of the function, it is a very basic list comprehension which calls our function f on every element of the list.

Let's try to run it with our partial function from before:

ghci> :l high-order.hs 
[1 of 1] Compiling Main             ( high-order.hs, interpreted )
Ok, one module loaded.
ghci> let addThree = add 3
ghci> myList = [1, 2, 3, 4, 5]
ghci> add2 addThree myList
[4,5,6,7,8]

Looks good ! But what if I do not want to create a (partial or not) function for this purpose ? We talked about lambda functions at the beginning of this article for a python example. Let's try it for Haskell:

ghci> add2 (\x->x+3) myList
[4,5,6,7,8]

Note that for lambdas, you need to wrap it between () and start with a \. The backslash is supposed to look like an actual Lambda (the Greek letter λ).

We could actually do the same without redefining an addition function using Haskell simple + infix operator:

ghci> add2 (+3) myList
[4,5,6,7,8]

Conclusion

Six down, around four more articles to go ! That's it for the higher order functions in Haskell. Now that we have a good understanding of it, we are going to discuss in our next article about the famous functions map, filter and foldl and how we can compose functions.

PS: Part 7 can be found here.

If you have a problem and no one else can help. Maybe you can hire the Kalvad-Team.