[Haskell-cafe] Josephus problem and style

[Ross Paterson]

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).