why is test for non-equality not working in this list comprehension?

user_907924 0
Viewed 52

In GHCi entering the following two lines returns a list of lists of two numbers from an input list of numbers such that all combinations are listed, but not using the same element twice.

Prelude> a = [1,3,7,10,25,50]
Prelude> [(x,y) | x <- a, y <- a, x /= y ]
[(1,3),(1,7),(1,10),(1,25),(1,50),(3,1),(3,7),(3,10),(3,25),(3,50),(7,1),(7,3),(7,10),(7,25),(7,50),(10,1),(10,3),(10,7),(10,25),(10,50),(25,1),(25,3),(25,7),(25,10),(25,50),(50,1),(50,3),(50,7),(50,10),(50,25)]

When I write similar code in my .hs program, the compiler keeps rejecting any guard which tests for Equality or Inequality. i.e.

choices :: [a] -> [[a]]
choices [] = [[]]
choices [x] = [[x]]
choices xs = [[m,n] |  m <- xs, n <- xs, m /= n ]

The compiler highlights the m /= n. Removing that guard (m =/ n) then the list comprehension works (with duplicate uses of elements of list a) Is this something to do with the compiler not knowing the type of m and n such that it can't assure they are in the type class Ord?

ghci typeclass list-comprehension haskell
2 Answers

Not all types are members of the Eq typeclass. For example you can not check if two IO Ints are equal.

You should specify a type constraint that specifies that this will work for all types that are a member of the Eq typeclass your implementation:

choices :: Eq a => [a] -> [[a]]
choices [] = [[]]
choices [x] = [[x]]
choices xs = [[m,n] |  m <- xs, n <- xs, m /= n ]

For the given sample input, we obtain:

Prelude> choices [1,3,7,10,25,50]
[[1,3],[1,7],[1,10],[1,25],[1,50],[3,1],[3,7],[3,10],[3,25],[3,50],[7,1],[7,3],[7,10],[7,25],[7,50],[10,1],[10,3],[10,7],[10,25],[10,50],[25,1],[25,3],[25,7],[25,10],[25,50],[50,1],[50,3],[50,7],[50,10],[50,25]]
user_675790

In case of doubt, you can always run the thing under the ghci interpreter:

$ ghci
 λ> 
 λ> choices xs = [[m,n] |  m <- xs, n <- xs, m /= n ]
 λ> 
 λ> choices [1,2]
 [[1,2],[2,1]]
 λ>

So far so good. But what type did ghci infer for the choices function ?

 λ> 
 λ> :type  choices
 choices :: Eq a => [a] -> [[a]]
 λ> 
 λ>

Voilà ! you have your missing type constraint.

GHC will not assume that type α offers some Ord or Eq interface, unless told so explicitely.

user_112824040
Related