On Sun, Apr 01, 2007 at 06:24:23PM +0200, Anthony Chaumas-Pellet wrote:
I've written a function to compute the general Josephus problem, giving both the number of the survivor and the order in which the others are killed. However, I am not overly fond of my actual Haskell implementation, so I would like some comments on elegance. My current function is as follow::
josephus k n = josephus' k 1 [1..n] [] where josephus' k i (x:xs) sorted | xs == [] = (x, reverse sorted) | i `mod` k == 0 = josephus' k (i+1) xs ([x] ++ sorted) | otherwise = josephus' k (i+1) (xs ++ [x]) sorted
You show a bias towards tail recursion. It would be neater (and lazier) to return the executed ones incrementally. This is easier if you don't distinguish the survivor from the rest, i.e. just put it on the end of the list. If you represent the circle with the sequence in Data.Sequence instead of a list, you reduce the cost of adding at the end, for a cost of O(k) per execution. But there's a cheaper way of rotating by k-1 elements (at least for large n and k). Instead of moving k-1 elements one at a time to the other end, you could split after (k-1) `mod` length xs elements and append the pieces in the opposite order, for a cost of O(log k).