Task Number Four Continued

Well what I am feeling my way towards is a Cartesian join between the list of heads of the list ns and the permutation of the tails, where the tail is the numbers in the list except the head one.

So this is where we go for a list comprehension:-

permutations :: [Int] -> [[Int]]
permutations ns = [ h:t | h <- ns, t <- permutations (ns except h) ]

That is too honey not to be right.  There are two generators: the first one cycles through the list of elements and the second one calls the function to get the permutations of the elements of the list except the element that the first generator has just pulled out itself.  This is legitimate as the generators are evaluated left-to-right.  This works in logic so it should work in  Haskell.

However I first need that except operator:-

except :: [Int] -> Int -> [Int]
except ns x = [ n <- ns, n /= x]

*Main> [50, 2, 1, 9] `except` 2
[50,1,9]

No hang on, that would eliminate more than I want:

*Main> [3, 1 , 4, 1, 5, 9] `except` 1
[3,4,5,9]

Just one 1 should go, not all of them.   Ok let's try spelling it out:

except :: [Int] -> Int -> [Int]
except [] x = []
except (n:ns) x =
    if n == x
    then ns
    else n : (ns `except` x)

*Main> [3, 1, 4, 1, 5, 9] `except` 1
[3,4,1,5,9]
*Main> [3, 1, 4, 1, 5, 9] `except` 3
[1,4,1,5,9]
*Main> [3, 1, 4, 1, 5, 9] `except` 9
[3,1,4,1,5]
*Main> [3, 1, 4, 1, 5, 9] `except` 8
[3,1,4,1,5,9]

I'm sure there are already library functions that do all this.

That's the one.  So.  Hang on let's generalise except to take any type where you can do an equality comparison:

except :: (Eq a) => [a] -> a -> [a]
except [] x = []
except (n:ns) x =
    if n == x
    then ns
    else n : (ns `except` x)

Now my permutations function:

permutations :: (Eq a) => [a] -> [[a]]
permutations [] = []
permutations xs = [ h:t | h <- xs, t <- permutations (xs `except` h) ]

The generalised version should work on strings:-

*Main> permutations "HORSE"
[]

No hang on it's not returning anything.

*Main> permutations [3,1,4,1,5,9]
[]

Hm.  Must have done something wrong.