[Haskell-cafe] Josephus problem and style

[Ross Paterson]

On Mon, Apr 02, 2007 at 09:12:17AM +1000, Duncan Coutts wrote:
> On Sun, 2007-04-01 at 16:46 -0400, Paul Hudak wrote:
> > 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]))
> 
> Lovely.
> 
> .. must.. resist ... urge to fuse ...

Resist -- there's little to gain from fusing an asymptotically slower
algorithm.  (This is O(n^2) compared with the original O(nk) and a
possible O(n log k).)