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.