Permutations of a list in Haskell

Using inductive

  1. Base case, an empty list has permutations: [[]]

  2. Suppose we have all permutations of a list, xs.

  3. If we were to add an element x to the head of the list, The permutations would be inclusive of x. Hence we will need to add all possible locations of x to each permutation.

  4. Since 1. is true, then 2. is true, then for any list, we can use step 3 to inductively construct all permutations. E.g. for [1,2,3,4] We construct for: a. [] b. 4:[] c. 3:4:[] and so on…

  5. Hence we obtain all permutations

perms [] = [[]]
perms (x:xs) = [zs | ys <- perms xs     -- We generate all the permutations of xs
                   , zs <- inserts x ys -- With x inserted at all possible locations in each permutation
               ]
  where
    inserts :: a -> [a] -> [[a]]
    inserts x [] = [[x]]
    inserts x (y:ys) = (x:y:ys) : map (y:) (inserts x ys)

Using recursive, helps with equational reasoning

perms = foldr step [[]] 
  where step x xss = concatMap (inserts x) xss
logo