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.

## No comments:

## Post a Comment