Potential rework of part 2.1 to reduce reliance on knowledge of other programming languages

[TheInnerLight]

Below is a suggested rework of part 2.1 to reduce the requirement of knowledge about Java, Python or other imperative programming languages and to focus instead on how Haskell would resolve the tail and non-recursive variations of a function.

I haven't raised this as a PR because trying to match the markup in the correct form looked like a nightmare and I presume you're using some program to generate the HTML anyway so it would probably also be less useful to you in that form.

I've retained some references to tail recursion allowing the generation of loops in machine code and being equivalent to loops in other languages but just reduced the prominence of that.

Please feel free to use this in whole or in part if you find any of it useful.

---

2.1 Recursion and Helper Functions

You saw in the previous chapter that you can create a factorial function:

factorial :: Int -> Int
factorial 1 = 1
factorial n = n * factorial (n-1)

Unfortunately, the above function isn't as efficient as it could be because Haskell has to resolve each part in multiple steps. These are the steps it goes through in order to do that:

factorial 5 = 5 * (factorial 4)
            = 5 * (4 * (factorial 3))
            = 5 * (4 * (3 * (factorial 2)))
            = 5 * (4 * (3 * (2 * (factorial 1))))
            = 5 * (4 * (3 * (2 * 1))))
            = 5 * (4 * (3 * 2)))
            = 5 * (4 * 6))
            = 5 * 24
            = 120

As you can see, Haskell has to retain a huge amount of state as it works through this calculation. This is absolutely fine if n is small but if n becomes large, it becomes increasingly inefficient and consumes lots of memory.

Were you to run print $ factorial 300000000, you could watch your task manager in horror as your simple program consumes several gigabytes of RAM!

Thankfully, you can write factorial in a slightly different way by storing the running total as you go along. Let's call this function factorial2 for now.

factorial2 :: Int -> Int -> Int
factorial2 1 total = total
factorial2 n total = factorial2 (n-1) (total * n)

Let's take a look at how this gets evaluated:

factorial2 5 1 = factorial2 4 (1 * 5)
               = factorial2 3 (5 * 4)
               = factorial2 2 (20 * 3)
               = factorial2 1 (60 * 2)
               = 120

In this version, the amount of work Haskell has to do to get to the answer is dramatically reduced and the amount of working state it needs to keep as it goes along is reduced even further.

This type of recursion where a function just directly calls itself with different arguments is called tail recursion. Tail recursion corresponds to loops in other programming languages. This is why tail recursion is often fast: the compiler can generate a loop in machine code when it sees tail recursion.

You still have one problem remaining at this point though, this new factorial function is much harder to use than the original, you have to remember each and every time you want to use it that you want to use it that you must call it with an extra argument of 1, e.g. factorial2 n 1. If you make a mistake and accidentally pass a number other than 1, you won't get the right answer.

There is a solution for this too and the answer is helper functions!

Let's rename the factorial2 function as factorialHelper.

factorialHelper :: Int -> Int -> Int
factorialHelper 1 total = total
factorialHelper n total = factorialHelper (n-1) (total * n)

You can then simply write a second function factorial which always calls factorialHelper with the requisite second argument of 1.

factorial :: Int -> Int
factorial n = factorialHelper n 1

Finally, with a bit of work, you've got a version that has both great performance and is easy and well-behaved to work with.

You could be forgiven for thinking at this point that recursion is only useful for maths equations but it's actually very handy for so-called utility functions as well.

Suppose that you wish to write a function that repeats a particular String n times, you can use a recursive function to facilitate this.

repeatString n str = repeatHelper n str ""

repeatHelper 0 _   result = result
repeatHelper n str result = repeatHelper (n-1) str (result++str)

repeatString 5 "ABC" would give the answer "ABCABCABCABCABC".

This is another example of a tail recursive function and something that you might expect to be a loop in a programming language like Java or Python.

Here is another example for computing Fibonacci numbers efficiently:

-- fibonacci numbers, fast version
fibonacci :: Integer -> Integer
fibonacci n = fibonacci' 0 1 n

fibonacci' :: Integer -> Integer -> Integer -> Integer
fibonacci' a b 1 = b
fibonacci' a b n = fibonacci' b (a+b) (n-1)

Sidenote: Haskell programs often use the apostrophe to name helper functions and alternative versions of functions. Thus the name fibonacci' for the helper function above. Names like foo' are usually read foo prime (like in mathematics).

I said earlier that this version of fibonacci is more efficient. Can you see why? The answer is that there are less recursive calls. The expression fibonacci' _ _ n calls fibonacci' _ _ (n-1) once, and this means that we can compute fibonacci' _ _ n in n steps.

[opqdonut]

Good stuff. I'll need to think about how I want to incorporate this into the material. I'd rather not talk (at this point) about performance too much, but rather about expressivity. I guess I need to figure out an example function that can't be implemented without a helper function.

[TheInnerLight]

Yeah, it's difficult, I had the same issues, I originally started by thinking about the repeatString function example but I realised that, without context, students would probably wonder why the function wasn't expressed differently as:

repeatString 0 _   = ""
repeatString n str = str ++ repeatString (n-1) str

It's not obvious why this version, that doesn't need a helper function, isn't better than the presented version that accepts the result because it more closely follows the recursion examples in the previous chapter.

This function, despite also being non-tail recursive, is far less obviously problematic compared to the factorial one, which you can at least observe has pathological memory behaviour by running it.

[asarkar]

After reading the problem description, it’s not clear to me where is the reliance on other programming languages. The first implementation of factorial isn’t efficient, sure, but nothing in it requires knowledge of other programming languages.

More practically, it is highly unlikely that Haskell is someone’s first encounter with a programming language. It is not taught as a primary language in computer science beginner courses, neither it is popular enough for someone to start learning on their own.