Re: Add 'subsequences' and 'permutations' to Data.List (ticket #1990)

David Benbennick wrote:

On Dec 18, 2007 12:56 PM, Bertram Felgenhauer wrote:

...

finally, we could make it slightly more lazy

Good point, your version is much better.

The same issue applies to permutations. I haven't had time to write out the code yet, but I can imagine a version of permutations that does: ...

Using mutual recursion between a version including the identity and one not including it, you can get: permutations1 :: [a] -> [[a]] permutations1 xxs = xxs : permutations3b xxs permutations1' [] = [] permutations1' (x:xs) = tail $ concatMap interleave $ permutations1 xs where interleave [] = [[x]] interleave (y:ys) = (x:y:ys) : map (y:) (interleave ys) Testing: > map (take 5) $ take 5 $ permutations1 [1..] [[1,2,3,4,5],[2,1,3,4,5],[2,3,1,4,5],[2,3,4,1,5],[2,3,4,5,1]] Again this has a call to tail. We have that tail $ concatMap interleave $ permutations1 xs = tail $ concatMap interleave $ (xs : permutations1 xs) = tail (interleave xs ++ concatMap interleave (permutations1 xs)) = tail (interleave xs) ++ concatMap interleave (permutations1 xs) So making a special case for "tail . interleave": permutations2 :: [a] -> [[a]] permutations2 xxs = xxs : permutations2' xxs permutations2' [] = [] permutations2' (x:xs) = interleave' xs ++ concatMap interleave (permutations2' xs) where interleave ys = (x:ys) : interleave' ys interleave' [] = [] interleave' (y:ys) = map (y:) (interleave ys) The next step would be to eliminate the (++) calls in interleave. This is not so easy, because of the last line, "map (y:) (interleave ys)". We can't use the ShowS trick here directly. The way out is of course to get rid of the map permutations3 :: [a] -> [[a]] permutations3 xxs = xxs : permutations3' xxs permutations3' [] = [] permutations3' (x:xs) = interleave' id xs $ foldr (interleave id) [] (permutations3' xs) where interleave f ys r = f (x:ys) : interleave' f ys r interleave' f [] r = r interleave' f (y:ys) r = interleave (f . (y:)) ys r And this is indeed a lot faster (ghc 6.8.1 -O2): time $ print $ sum $ map sum $ permutations $ [1..10] permutations2: 3.875000 sec permutations3: 1.625000 sec Unfortunatly, the clarity of the algorithm has not improved. Twan