🕵️‍♀️ The Secret Life of Function Application in Haskell (Part 1)

These days, we all lead busy lives. The spirit of these two articles (Part 1 & Part 2) is to give people who have played around with Haskell, but never thought about how Haskell programs are executed, a better feel for what’s going on the next time they run a Haskell program.

Trivia Time ⏳

How many arguments does the function below in Haskell take?

fn :: Int -> Int -> Int -> Int
fn arg1 arg2 arg3 = arg1 + arg2 + arg3

Answer. 1

Huh? What kind of trickery is this? 🤷‍♂️ It clearly has 3 arguments. It even says arg1 , arg2 , arg3 ! Now, usually at this point, someone will tell you that in Haskell, all functions are curried by default. You’ll then ask what on earth is currying, shortly followed by why the name curry, and depending on who you ask, you’ll get a different answer.

I digress! Currying is the process of transforming a function in a way, such that even if you defined it to have 3 arguments, like in the case for fn, it will actually be a function that when called with the first argument, returns a function that will accept the second, and so on until the last argument is passed to fn, where it will eventually evaluate arg1 + arg2 + arg3 .

Want to learn Haskell? So do we! At Picket Studio, we’ve started a YouTube playlist of us having a bunch of fun working through the fabulous Haskell course put together by Tony Morris & Mark Hibberd 👏.

Okay, back to to the mysterious world of function application! Even though we now know that currying is responsible for the trickery, it still feels largely like magic 🧙‍♀️! If we were to do fn 3 4 , where do the arguments 3 and 4 live until we get arg3 ? And how does the function returned from fn 3 4, know where to get the 3 and 4 from when it’s called? Is that something the Haskell runtime is managing for us behind the scenes?

Turns out it comes down to some sweet sweet syntactic sugar 🍭🍦. If we have:

fn1 arg1 = arg1 + 1

Haskell says that is cute, but I’m going to convert that to the ƛ version. In other words, I’m going to curry the function. So under the hood, it’ll look like:

fn1 = \arg1 -> arg1 + 1

That is, we now have a named binding called fn1 which equals an anonymous function (a.k.a lambda expression, the \ is a poor man’s ƛ), which takes one argument arg1 and returns the expression arg1 + 1. Okay, that’s all well and good for a function with only 1 argument, what about a function with more arguments? Bring in fn2 😎

fn2 arg1 arg2 = arg1 + arg2

Surely that takes two args? Not if Haskell can change that. It does the same conversion trick, and converts fn2 to:

fn2 = \arg1 -> \arg2 -> arg1 + arg2

That is, we now have another named binding called fn2 that takes the argument arg1 and returns another function \arg2 -> arg1 + arg2.

Now, let’s define a slightly more involved function named foo , and take a casual stroll ️🚶‍♀️all the way from its definition to it finally returning a value:

foo :: Int -> Int -> Int -> Int
foo x y z = x + y * z

If we apply the conversion trick that we’ve come to love (or despise, up to you), foo is actually defined as:

foo = \x -> \y -> \z -> x + y * z

So when we call foo 3 4 5, what actually happens is:

foo 3 4 5
  = (foo 3) 4 5                            (1)
  = ((\x -> \y -> \z -> x + y * z) 3) 4 5  (2)
  = ((\y -> \z -> 3 + y * z) 4) 5          (3)
  = (\z -> 3 + 4 * z) 5                    (4)
  = 3 + 4 * 5                              (5)
  ...

Let’s pull up here for a sec! 🤔 What is interesting to note is that when Haskell tries to evaluate foo 3 4 5, it ends up playing a continual game of substitution. Notice how on line (2), where we have the lambda expression (\x -> \y -> \z -> x + y * z) and its argument 3. Haskell very kindly applies the lambda expression to the argument 3, which has the result of replacing all instances of the parameter x with 3. It then does the same kind of dance 🕺 on line (3) with (\y -> \z -> 3 + y * z) and 4, and so on for (\z -> 3 + 4 * z) and 5 on line (4) .

This kind of dance has a name, it’s not disco, but close, it’s beta-reduction. It might be a fancy word (and even fancier when used with the letter β), but it has a plain old definition. It’s called that because if you ever find yourself with a lambda expression and it’s argument, and you apply the lambda to the argument, you will reduce the size of the expression. Not convinced? Take the lambda expression from line (2) again:

((\x -> \y -> \z -> x + y * z) 3)

and let’s see what happens when we apply the lambda to the arg 3 :

(\y -> \z -> 3 + y * z)

Tada! See how it became smaller! We achieved this by substituting x with 3 and then returning the lambda expression on the right hand side of \x ->. That’s all there is to beta-reduction! Oh, why the word beta? That’s due to the fact that there was already a related thing called alpha-reduction, and so the next letter in the greek alphabet after alpha is beta (I thought we were done with the trivia…).

Okay, back to evaluating foo 3 4 5! Where were we? That’s right, 3 + 4 * 5 on line (5). Now, it might seem immediately obvious to us that it’s 23, but poor old Haskell doesn’t know a thing about arithmetic. All it sees is two functions named (+) and (*), and says, hmm, which one should I apply first? But! I think we can all agree, that’s already a lot of beta-reductions for a single article.

You’ve now got a feel for beta-reductions, meaning you’ve got everything you need in your toolbox 🧰 to solve the deceivingly simple question:

How does Haskell evaluate the expression 3 + 4 * 5 ?

To find out if your intuitions are on the right track, check out Part 2!

🕵️‍♀️ The Secret Life of Function Application in Haskell (Part 2)

If you are anything like us, Haskell can seem esoteric at times! To help make sense of it, we’ve been having a bunch of fun working through the fabulous Haskell course put together by Tony Morris & Mark Hibberd 👏. We’ve even got a YouTube playlist where we go through the course in realtime, if that’s up your alley 🛒.