[Haskell-cafe] Josephus problem and style

[Paul Hudak]

Here's a solution that I think is a bit more elegant.

    -Paul

 josephus n k =
     let loop xs = let d:r = drop (k-1) xs
                   in d : loop (filter (/= d) r)
     in take n (loop (cycle [1..n]))


Anthony Chaumas-Pellet wrote:
> 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