Implementing functions that generate permutations and derangements is like a baptism ritual for every Haskell newbie. So, let’s try to give implementations for the following four functions:

• isPermutation – checks if a given list is a permutation of another
• perms – generates the permutations of a given list
• isDerangement – checks if a given list is a derangement of another
• deran – generates the derangements of the list [0..n]

Task 1. Create a isPermutation function that takes two lists and returns True if the arguments are permutations of each other.

Solution 1. The function should take two lists of type a and return a Boolean, so its declaration should look like [a] -> [a] -> Bool. One implementation will be to iterate over the elements of the first list and check if each of these appears in the second list. In pseudo code the recursion will look like this:

1. Take the first element in arg1
2. If it does not exist, return False. If it exists in arg2, delete it.
3. Apply steps 1 and 2 for the all but the first elements in arg1 and the rest of the elements in arg2

Note that if arg1 is a permutation of arg2 the two lists should have the same length each time we compare them.

isPermutation :: Eq a => [a] -> [a] -> Bool
isPermutation [] [] = True
isPermutation xs (y:ys) | length xs /= length (y:ys) = False
                        | otherwise = isPermutation (delete y xs) ys

Task 2. Create a function perms that takes a list with no duplicate elements and generates all permutations of that list.

Solution 2. The function has one parameter of type list and returns a list of lists, so its declaration should be [a] -> [[a]]. The suggested implementation uses list comprehension to iterate over each of the elements of the list and recursion to append the rest of the elements.

perms :: Eq a => [a] -> [[a]]
perms [] = [[]]
perms xs = [ i:j | i <- xs, j <- perms $ delete i xs ]

Task 3. Create a function isDerangement that takes two lists and checks if the second is a derangement of the first.

Solution 3. The function takes two lists and returns a Boolean, so its declaration should be [a] -> [a] -> Bool. The implementation below ensures that the two lists are permutations and applies additional constraint using the index helper function.

isDerangement :: Eq a => [a] -> [a] -> Bool
isDerangement [] [] = True
isDerangement xs ys = and [ x `elem` ys && (index x xs /= index x ys) | x <- xs ] where
      index n (x:xs) | n == x = 0
                     | otherwise = 1 + index n xs

Task 4. Create a function derangements that generates a list of all derangements of the list [0..n]

Solution 4. The function takes a single integer value and returns a list of lists of integers, so its declaration should be Int -> [[Int]]. The following example uses the perms and isDerangement functions and filters all generated permutations for which the isDerangement function returns True.

deran :: Int -> [[Int]]
deran n = filter (\ p -> isDerangement p [0..n-1]) (perms [0..n-1])