Data.List.permutations

(J. Waldmann, December 2021)

I was wondering what the code for Data.List.permutations https://hackage.haskell.org/package/base-4.16.0.0/docs/src/Data.OldList.html#permutations does, and how it came to be.

-- | The 'permutations' function returns the list of all permutations of the argument.
--
-- >>> permutations "abc"
-- ["abc","bac","cba","bca","cab","acb"]
permutations            :: [a] -> [[a]]
permutations xs0        =  xs0 : perms xs0 []
  where
    perms []     _  = []
    perms (t:ts) is = foldr interleave (perms ts (t:is)) (permutations is)
      where interleave    xs     r = let (_,zs) = interleave' id xs r in zs
            interleave' _ []     r = (ts, r)
            interleave' f (y:ys) r = let (us,zs) = interleave' (f . (y:)) ys r
                                     in  (y:us, f (t:y:us) : zs)

Some references:

• my analysis (Dec 2021) https://mail.haskell.org/pipermail/haskell-cafe/2021-December/134921.html, written without knowing about:
• Twaan van Laarhoven (July 2014) https://stackoverflow.com/questions/24484348/what-does-this-list-permutations-implementation-in-haskell-exactly-do/24564307#24564307, referring to
• GHC ticket https://gitlab.haskell.org/ghc/ghc/-/issues/1990 (December 2007)
• discussion on libraries (December 2007) https://mail.haskell.org/pipermail/libraries/2007-December/008788.html referring to
• Haskell 1.3 Library Report (July 1996) https://web.archive.org/web/20060620221455/http://haskell.cs.yale.edu/haskell-report/List.html as the original source.

The original code (1996) was

-- 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)

The example shows that semantics did change.