[Haskell-cafe] permutations and performance

[John D. Ramsdell]

On Sun, Aug 17, 2008 at 11:27 AM, Yitzchak Gale <gale at sefer.org> wrote:

> There, Twan van Laarhoven designs the implementation
> of the permutations function that is slated to be included in
> GHC 6.10.

I look forward to Twan's design.  I found the Haskell 1.3 definition.

> -- permutations xs returns the list of all permutations of xs.
> -- e.g., permutations "abc" == ["abc","bac","bca","acb","cab","cba"]
> permutations            :: [a] -> [[a]]
> permutations []         =  [[]]
> permutations (x:xs)     =  [zs | ys <- permutations xs, zs <- interleave x ys ]
>   where interleave          :: a -> [a] -> [[a]]
>         interleave x []     =  [[x]]
>         interleave x (y:ys) =  [x:y:ys] ++ map (y:) (interleave x ys)

I like the use of list comprehension, but I was surprised the last line was not:

>         interleave x (y:ys) =  (x:y:ys) :  map (y:) (interleave x ys)

John