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

Haven’t read Part 1 yet? Not a problem! Feel free to jump over there first, and then come back to enjoy the rest. Otherwise, if you are only here to see how Haskell in all its glory evaluates the expression 3 + 4 * 5 , then as you were!

Trivia Time ⏳

Which expression is more performant in Haskell? 1 + 2 or (+) 1 2 ?

…

Answer.
It’s a trick question 🎩. They are exactly the same.

How then does Haskell know then that + and (+) refer to the same function? Well! I’m glad you asked. It turns out that we have more of that sweet sweet syntactic sugar 🍭🍦 to thank. There’s a nice rule in Haskell that says if the name of the function is enclosed with () and the name inside the parentheses starts with a non alphanumeric character, than Haskell will assume that the name inside the parentheses is an infix operator.

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 👏.

That was bit of a mouthful, to see what it means in practice, let’s pretend that Haskell didn’t have a function for multiplication. Our job then is to define such a function, and we want to use the symbol* for the infix operator (so we can do a * b). How would one go about doing that? 🤷‍♂️ Together with the fact that we have a function for addition (+), and that we can simply view multiplication as repeated addition, we can go on to define (*) as:

(*) :: Int -> Int -> Int
(*) a 0 = 0                     -- (i)
(*) a 1 = a                     -- (ii)  
(*) a b = (*) (a + a) (b - 1)   -- (iii)

Quick test to check that it works? Let’s try (*) 1 2:

x = (*) 1 2
  = (*) (1 + 1) (2 - 1)       -- by eqn ii [a = 1, b = 2]
  = (*) (1 + 1) 1             -- by assumed defn of (-)
  = (1 + 1)                   -- by eqn iii [a = (1 + 1)]
  = 2                         -- by assumed defn of (+)

Looks good! Now, because we’ve named the function to be called (*), and * is non alphanumeric, Haskell has assumed that * is an infix operator for the same function:

x = 2 * 10
putStr x -- 20

When Haskell sees *, it says, hang on a minute, I know exactly what function that is referring to. It then takes the left hand side, 2 in this case, and maps it to the arg a, then likewise for the right hand side, 10, for the arg b. So as far as Haskell is concerned, 2 * 10 and (*) 2 10 are equivalent.

Now, in Part 1, we took a breather when we got to the expression 3 + 4 * 5. It’s now time to run back on the field and tackle the rest of the evaluation! 🤾‍♀️ For those who missed Part 1, we defined a simple function called foo :

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

and then tried applying foo to 3 4 5:

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)
  ...

To us, it seems immediately obvious that the expression 3 + 4 * 5 evaluates to23, but poor old Haskell doesn’t know a single thing about arithmetic. All it sees is two ordinary operators (which we know are actually functions behind the scenes) named + and *, and says, hmm, which one should I apply first? To decide this burning question, it needs to find out which function has a higher precedence. If we had explicitly grouped (3 + 4) or (4 * 5), Haskell wouldn’t have to figure this out, but right now it’s ambiguous.

To find out which one Haskell will apply first, we can consult the much beloved GHCi, using the :i command, for both (+) and (*) .

> :i (+)
class Num a where
  (+) :: a -> a -> a
  ...
  	-- Defined in 'GHC.Num'
infixl 6 +

We can see it says that (+) is an infix function, left associative (the l after infix ) and has a precedence of 6. Compare this to (*) :

> :i (*)
class Num a where
  ...
  (*) :: a -> a -> a
  ...
  	-- Defined in 'GHC.Num'
infixl 7 *

It is also infix and left associative , but has a precedence of 7! So (*) wins, as it has a higher precedence than (+). Winning here, simply means that when given the choice between (+) or (*), Haskell will always choose to first apply (*) . In other words, there is an invisible set of parentheses in the expression 3 + 4 * 5, which is(3 + 4) * 5.

We saw in Part 1, that if you’ve got a function and it’s argument, you can substitute the argument into the function (known by the very fancy term, beta-reduction). Take lines (4) and (5) for example.

   ...
   = (\z -> 3 + 4 * z) 5                    (4)
   = 3 + 4 * 5                              (5)

See how we substituted 5 for z in 3 + 4 * z. Well, because we know that (*) will be applied first, let’s try and do the same thing with (*) and its first arg (3 + 4). But! We’ve got a little problem. We don’t know how (*) (or (+) for that matter) is defined in Haskell. Without it, we can’t possibly know what to substitute (3 + 4) for. However! We can use our very own version of (*), which we luckily defined earlier:

(*) :: Int -> Int -> Int
(*) a 0 = 0                     -- (i)
(*) a 1 = a                     -- (ii)  
(*) a b = (*) (a + a) (b - 1)   -- (iii)

Taking that definition, we can progress a little further! 🔦 So, Haskell looks at 3 + 4 * 5, and says, I know that (*) has a higher precedence, so I’ll apply it first. In other words, Haskell decides to do (3 + 4) * 5, as opposed to 3 + (4 * 5). Where to now though? It doesn’t seem obvious how you would pattern match (3 + 4) * 5 with the third definition for (*), namely a b = (a + a) * (b — 1). But, remember, we can always convert between the infix and prefix forms of the expression. So let’s do that here! So (3 + 4) * 5 becomes (*) (3 + 4) 5. That’s looking much closer to definition iii. We now have:

foo 3 4 5
  ...
  = 3 + 4 * 5                              (5)
  = (*) (3 + 4) 5                          (6)

The stage is set! We are ready apply (*) to its first argument (3 + 4), but the lambda expression is nowhere in sight? That’s because it is hiding in disguise. In Part 1, we saw that in Haskell, if we had a function foo defined as:

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

Haskell will transform that (known as currying) into a named binding called foo which is assigned to the lambda expression that takes the first argument x, like so:

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

Well! We can do the exact same conversion to our definition of (*). The only difference is that the definition for (*) has three cases that we need to worry about, not just the one like we had for foo. We need to employ a case expression in Haskell, to decide which case to apply! This case applied solely depends on the value of b. Even though we defined (*) as :

(*) :: Int -> Int -> Int
(*) a 0 = 0                     -- (i)
(*) a 1 = a                     -- (ii)  
(*) a b = (*) (a + a) (b - 1)   -- (iii)

Haskell says, I love what you are doing there, but I like to deal in the currency of lambda expressions ƛƛƛ, so I’m going to convert your definition to the curried equivalent:

(*) = \a -> \b -> case b of
                       0 -> 0                   -- (i)
                       1 -> a                   -- (ii)
                       _ -> (*) (a + a) (b - 1) -- (iii)

Woah! Slow down a little Haskell. What’s going on here? Granted, it’s not as aesthetically pleasing as our definition, but it’s saying the exact same thing. That is, I’m a function, that once applied to two arguments, a and b, depending on the value of b, I’ll decide to return either 0, a, or recurse. The beauty of this definition is that we’ve got ourselves a lambda expression that we can apply to the first argument of (*), which was (3 + 4). So we can literally swap (*) for it’s value, a.k.a, the lambda expression:

foo 3 4 5
  ...
  = 3 + 4 * 5                                                 (5)
  = (*) (3 + 4) 5                                             (6)
  = (\a -> \b -> case b of
                      0 -> 0                   
                      1 -> a                   
                      _ -> (*) (a + a) (b - 1)) (3 + 4) 5     (7)

Almost there! It’s finally time to do the substitution dance we’ve all been patiently waiting for with lambda expression for (*) and the argument (3 + 4):

foo 3 4 5
  ...
  = 3 + 4 * 5                                                  (5)
  = (*) (3 + 4) 5                                              (6)
  = (\a -> \b -> case b of
                      0 -> 0                   
                      1 -> a                   
                      _ -> (*) (a + a) (b - 1)) (3 + 4) 5      (7)
  = (\b -> case b of
                      0 -> 0                   
                      1 -> (3 + 4)                
                      _ -> (*) ((3 + 4) + (3 + 4)) (b - 1)) 5  (8)

See how we replaced all occurrences of the argument a, on line (7), with the expression (3 + 4), giving us line (8). We can now repeat the process for next argument b.

foo 3 4 5
  ...
  = 3 + 4 * 5                                                  (5)
  = (*) (3 + 4) 5                                              (6)
  = (\a -> \b -> case b of
                      0 -> 0                   
                      1 -> a                   
                      _ -> (*) (a + a) (b - 1)) (3 + 4) 5      (7)
  = (\b -> case b of
                      0 -> 0                   
                      1 -> (3 + 4)                
                      _ -> (*) ((3 + 4) + (3 + 4)) (b - 1)) 5  (8)
  = (case 5 of
          0 -> 0                   
          1 -> (3 + 4)                
          _ -> (*) ((3 + 4) + (3 + 4)) (5 - 1))                (9)
  = (*) ((3 + 4) + (3 + 4)) (5 - 1)                            (10) 

It’s just like clockwork! ⏱ It’s fun to think of it as with each tick of the clock, an argument is applied, changing the shape of the expression each time. It’s interesting that once we applied the lambda on line (8), to the arg 5, we were left with a case expression on line (9). The case expression first compared 5 to 0, and said, nope! Then it tried 1, and failed, leaving it no choice but to return (*) ((3 + 4) + (3 + 4)) (5-1). Which is correct! We expect to recursively call (*) until the arg b is 1 or 0.

On line (10), it’s all setup to again play the same game with (*), but this time with the argument ((3 + 4) + (3 + 4)), as opposed to 3 + 4 which we had last time. To spare you the monotony of running through each step until b = 1, we can see that during each recursive call of (*), we subtract 1 from b. So, at some point b will equal ((((5–1)-1)-1)-1):

= (*) ((3 + 4) + (3 + 4)) (5 - 1)                            (10)
= ...
= (*) ((3 + 4) + ...) ((((5 – 1) - 1) - 1) - 1)
= ...
= (case ((((5 – 1) - 1) - 1) - 1) of
        0 -> 0                   
        1 -> (3 + 4)                
        _ -> (*) ((3 + 4) + (3 + 4)) (5 - 1))                (11)
= (case 1 of
        0 -> 0                   
        1 -> ((3 + 4) + ...)                
        _ -> (*) ((3 + 4) + (3 + 4)) (5 - 1))                (12)
= ((3 + 4) + ...)                                            (13)

🥳 We at last hit the base case for (*), returning (3 + 4) added to itself 5 times! In other words, we’ve got:

foo 3 4 5
  ...
  = (((((3 + 4) + (3 + 4)) + (3 + 4)) + (3 + 4)) + (3 + 4))

And that’s just about as close as we can get to the real thing! At this point, Haskell says enough of these seemingly endless substitutions (beta-reductions), I’m going to politely ask the CPU to execute an add instruction for me and be done with it.

🎉 Fun Fact

In Haskell, you can define functions using the infix form as well. So, we could have equally defined (*) as:

(*) :: Int -> Int -> Int
a * 0 = 0                   -- (i)
a * 1 = a                   -- (ii)  
a * b = (a + a) * (b - 1)   -- (iii)

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 🛒.