Recursions

I have to start this blog by delivering bad news: there are no for loops in Haskell. You might be asking, "How do we achieve loops then?" In Haskell, loops can be achieved by using recursions. This is one of the many reasons why learning Haskell is fun and rewarding; it forces you to think recursively instead of blindly using for loops for everything. Let's look at an example of a factorial function that computes the factorial of a number.

factorial :: Integer -> Integer
factorial n = 
    if n == 1 then 1 --- base case
    else n * factorial (n-1)

How elegant! (For beginners who are not sure about recursion, check out an awesome video by North Bay Python, Recursion for Beginners: A Beginner's Guide to Recursion. )

Guards

In Haskell, you need to write a lot of recursions, but writing if statements for every case in every function can be quite verbose. That's where guards come into play. Let's refactor the factorial function using guards.

factorial n
    | n <= 1 = 1 --- base case
    | otherwise n * factorial (n-1)

otherwise is always evaluated to True in Haskell, so it can be used as else.

Accumulators

In Haskell, there is another way of implementing recursion. Here is the way for the factorial function.

factorial n = aux n 1
  where
    aux n acc
        | n <= 1 = acc
        | otherwise = aux (n-1) (n*acc) 
        --- aux (n-1) $! (n*acc) for strictly evaluating (n*acc) and fully prevent stack overflow?
        --- If you are a good Haskeller, please reach out and lmk if $! is necessary. 

I hear some of you say, "Wait a minute, where is the elegance? You just made it unnecessarily more complicated." Yes, it is complicated, but I have to tell you that this is the optimal way of implementing the factorial function. For some folks who are confused as to why this is the optimal recursion, I will give you the Python equivalent of the above algorithm.

def factorial (n: int):
  acc = 1
  while True:
    if n <= 1:
      return acc
    else:
      acc = n * acc
      n = n - 1

As you can see from the above, it uses acc (or accumulator) to store the result of the previous iteration of the while loop, thereby avoiding calling the factorial function inside of the factorial function. This is called tail recursion and can avoid the classic stack overflow problem. (For beginners who are not sure about tail recursion and stack overflow, check out an awesome video by North Bay Python, Recursion for Beginners: A Beginner's Guide to Recursion. )

The compilers of some languages like Python and C do not support tail call optimization, but GHC for Haskell does. This means normal recursive functions are converted into tail recursive functions by GHC if it is appropriate to do so. However, I personally think you cannot fully rely on compilers to optimize your code, and you should have sufficient knowledge regarding this. (Not that I know a lot about this stuff. Tail recursion is not a one-size-fits-all solution, and it can make the algorithm worse. Be sure to really analyze the problem at hand when applying recursion.)

Pattern Matching

Aside from the above, Haskell allows us to do something like the following:

isZero 0 = True
isZero _ = False

Unlike other languages that override the function definition when something like the above is done, Haskell can perform pattern matching on the input and run corresponding operations. The _ character is used to indicate any values except for the ones mentioned previously.

Exercises

This is an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #3 - Recursions, Guards, Patterns. YouTube.