[Haskell-cafe] permutations and performance
John D. Ramsdell
ramsdell0 at gmail.com
Sun Aug 17 22:34:29 EDT 2008
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)
More information about the Haskell-Cafe