32leaves.net
Cool, you're reading my blog. Hope you like it. You may wanna check my twitter page, too

Note to myself: tail recursion in Haskell does not allow me to stop thinking

November 6, 2009 – 9:04 pm
We’ve propably all heard that tail recursion is the way to go. That’s true, but as I’ve learned today applying this principle does not free you from thinking about your code.
The task was to implement the Josephus game. That’s particularly straight forward in imperative languages such as Java:

1
2
3
4
5
6
7
8
9
10
11
12
13
private int josephus(int amountOfSoldiers, int interval) {
    List<Integer> soldiers = new LinkedList<Integer>();
    for(int i = 1; i <= amountOfSoldiers; i++) soldiers.add(i);
   
    int index = 1;
    while(soldiers.size() != 1) {
        for(Iterator<Integer> iter = soldiers.iterator(); iter.hasNext() && iter.next() != null; ) {
            if(index++ % 3 == 0) iter.remove();
        }
    }
   
    return soldiers.get(0);
}
But Java is not much of a challange, so lets give this a shot in Haskell:

1
2
3
4
5
6
7
8
9
10
11
12
13
josephus :: [Int] -> Int
josephus []  = 0
josephus [x] = x
josephus l   = josephus_ l 1 where
    josephus_ [x] _ = x
    josephus_ xs o  = let
        len = length xs
        off = ((o + len) `mod` 3) in
        josephus_ (dropByInject o xs) off

dropByInject _ []     = []
dropByInject m (x:xs) | m `mod` 3 == 0 = dropByInject (m + 1) xs
                      | otherwise      = x:(dropByInject (m + 1) xs)

Obviously the dropByInject function is not tail recursive. When we call the following program

1
main = putStrLn (show [josephus [1..l] | l <- [1..2000]])

which computes the “Josephus number” from 1 to 2000 soldiers, takes roughly 0.792s.

So I did a second shot which is tail recursive:

1
2
3
dropByInject r _ []     = r
dropByInject r m (x:xs) | m `mod` 3 == 0 = dropByInjectAp r (m + 1) xs
                        | otherwise      = dropByInjectAp (r ++ [x]) (m + 1) xs

. And here is where I stopped thinking – which immediately became clear to me as the same task as above takes 23.791s. Wow, that’s not really better than the 0.792s of the not-tail-recursive version. So why is that:
if we take a look at how the list is constructed in the otherwise part of the dropByInject function we see that the x is appended to the end of the list via

1
(r ++ [x])

. And that was the mistake – lists in Haskell are linked lists and appending to linked lists takes \mathcal{O}(n) as we have to find the end of the list first. Upps

Alright, let’s go for a third shot:

1
2
3
dropByInject r _ []     = reverse r
dropByInject r m (x:xs) | m `mod` 3 == 0 = dropByInjectTr r (m + 1) xs
                        | otherwise      = dropByInjectTr (x:r) (m + 1) xs

This version takes only 0.704s. That’s not lightyears of speed gain compared to the first version, but hey at least it’s tail recursive.

By Christian | Posted in Development | Tagged , | Comments (0)

Leave a Reply