From pseudo-code to Haskell (Part 1)

People sometimes say that Python is executable pseudo-code. Maybe because it’s a language that’s relatively light on line noise with a lot of nice built-in functions that convey the intent of what you’re trying to do, and you can write it in a straight-forward way without getting too bogged down in ancillary details.

The same is not often said about Haskell, but actually it can be a very effective pseudo-code executer as well! Consider a simple problem of finding the least common multiple of two positive numbers.

A simple example

The least common multiple of $a$ and $b$, commonly written $lcm(a,b)$, is the smallest positive integer in the shared multiples of $a$ and $b$. Translating directly from that definition, a simple pseudo-code implementation could look something like this:

lcm a b = minimumCommon (multiplesOf a) (multiplesOf b)

Let’s consider this multiplesOf function. The positive multiples of $a$ is just $ 1 a,2 a,3a,…$, so multiplesOf should be some kind of function that takes a number and gives an infinite list of all the multiples of that number. It would also be handy to have that infinite list be sorted so that the multiples are in increasing order. Still writing pseudo-code, that might look like this:

multiplesOf a = (multiplyBy a) eachOf [1,2..]

But this is nearly legitimate Haskell. All we need is to do is to replace the words multiplyBy and eachOf with the actual function names:

multiplesOf a = (* a) `map` [1,2..]

Notice that this list of multiples will naturally be in increasing order. This is important for our next step: figuring out the common numbers from two lists of numbers.

Given two sorted, infinite lists of numbers, a simple way to find their common elements is to operate recursively on their heads. There are only three cases to take care of:

  1. If the heads of both lists are equal, then we have found a common element, so keep that and find the common elements in the tails of both lists.

  2. If the first is smaller than the second, then we should throw away the head of the first list, and find the common elements between the tail of the first list and all of the second list.

  3. If the first is larger than the second, then do the opposite of (2).

The code itself is much more succinct:

common (x:xs) (y:ys)
    | x == y = x : common xs ys
    | x < y = common xs (y:ys)
    | y < x = common (x:xs) ys

Finally, there’s just the business of finding the minimum element in this list. This is easy because the list is already sorted, so we can just take the first element and call it day.

minimumCommon xs ys = head (common xs ys)

With all this in place, our pseudo-code implementation of lcm above is valid Haskell:

lcm a b = minimumCommon (multiplesOf a) (multiplesOf b)

Check the edge cases

What happens if we try to evaluate lcm 0 5? It will never terminate, since one of the lists will be $[0,0,0,…]$ and the other list will be $[5,10,15,…]$, so they don’t have a common element.

This isn’t really a bug, per-se, since we intentionally defined this function to work only on positive numbers. This function is undefined on any other input, and an infinite loop is one way to return an error, though to be honest it is not the best way. An alternative is to use the Maybe type to return Nothing when we pass negative numbers to our function.

lcm2 a b
    | a > 0 && b > 0 = Just $ minimumCommon (multiplesOf a) (multiplesOf b)
    | otherwise      = Nothing

Next time

Of course, this implementation will not be the fastest lcm in the world, but it’s hard to beat its clarity. You can look at get a pretty good idea of what this function is going to do just by looking at it. 1

But maybe we just got lucky picking a trivial example. In Part 2 of this series, we’ll start looking at a much more interesting example: solving Sudoku puzzles.

  1. That isn’t to say that you shouldn’t comment it!
June 16, 2017