Permutations of a list in Haskell
Base case, an empty list has permutations:
Suppose we have all permutations of a list, xs.
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.
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…
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