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); } |

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

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

1 2 3 |

. 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

as we have to find the end of the list first. Upps

1 2 3 |

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.