[Haskell-cafe] Josephus problem and style

[Anthony Chaumas-Pellet]

Hello,

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

The biggest difficulty I had is representing the circle (a continuous
unit, unlike the list). The only solution I've found is to explicitly
concatenate lists during each iteration, using an index to check
whether the current element should be kept.

It seems to me that manupilating lists so often makes the resulting
function unclear, and hides the basic principle behind the Josephus
sequence. So, I'm looking for a better way to write this function, but
enlightenment eludes me.

I've taken up Haskell in earnest a couple weeks ago, after a fairly
long stay in Lisp land (perhaps it shows). My previous "Eureka!"
moment in Haskell was matrix multiplication, along the lines of:

matProd a b = [[sum (zipWith (*) x y) | y <- transpose b]| x <- a]

Thanks!
Anthony Chaumas-Pellet