Thanks for your comments everyone! There is one point that has left me puzzled, though. From: Ross Paterson

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.

Why is tail recursion a bad thing for a finite function? (Of course, it would be... curious on functions that can produce infinite results) Is tail recursion simply not the most common Haskell idiom, or is there some technical reason I fail to see? Anthony Chaumas-Pellet

Malcolm Wallace wrote:

Anthony Chaumas-Pellet wrote:

...

Why is tail recursion a bad thing for a finite function? Is tail recursion simply not the most common Haskell idiom, or is there some technical reason I fail to see?

Tail recursion tends to create space-leaks, which in turn hurt time performance.

That's only part of the truth. Take for example the ordinary version of and :: (a -> Bool) -> [a] -> Bool and p [] = False and p (x:xs) = p x && and xs and it's tail-recursive cousin and' p [] b = b and' p (x:xs) b = and' p xs (b && p x) Apparently, the function is True if there is some element in the list that fulfills the condition p. Clearly, we can stop traversing the list when we find the first element that satisfies p. Now, the tail-recursive version is doomed to traverse the entire list, but thanks to lazy evaluation, the ordinary version stops as soon as an element x with p x is found. Of course, one could alter the definition of and' to achieve early stopping and' _ _ True = True and' p (x:xs) False = and' p xs (p x) and' _ [] False = False but this is not advisable: we unfolded the definition of (&&). In the ordinary case however, (&&) already contains all the magic of early stopping, the recursion scheme has nothing to do with it. Thus, the most common Haskell idiom about tail recursion is to not think about it (and hence not use it). Instead, return values as early as possible (in some cases (&&) can return a definite answer by looking at the first argument only). Note that this is very different from strict functional languages. Regards, apfelmus

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 ... Actually the interesting thing that makes this example tricky to fuse using automagic techniques is that while loop looks like it should be a good producer and consumer, it's also recursive. Hmm, interesting. Duncan