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

[Twan van Laarhoven]

Chris Kuklewicz wrote:
> Unfortunately, permutations5 has an error:
> 
> 
>>*Main> permutations5 [1..3]
>>[[1,2,3],[2,1,3],[3,2,1],[3,3,1],[3,2,2],[3,3,2]]
>>*Main> permutations6 [1..3]
>>[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

Oops, the "map (x:) ..." in interleave should be "map (y:) ...",

  permutations5 xs = xs : perms xs [[]]
    where
     perms []     ps = []
     perms (x:xs) ps = concatMap interleave' ps
                    ++ perms xs
                      (concatMap interleave  ps)
      where interleave  []     = [[x]]
            interleave  (y:ys) = (x:y:ys)     : map (y:) (interleave  ys)
            interleave' []     = []
            interleave' (y:ys) = (x:y:ys++xs) : map (y:) (interleave' ys)

Twan