# Implementing Haskell's \\ (Set Difference)

Learn You a Haskell presents the \\ function.

\\ is the list difference function. It acts like a set difference, basically. For every element in the right-hand list, it removes a matching element in the left one.

Example:

ghci> [1..10] \\ [2,5,9]
[1,3,4,6,7,8,10]


setDifference :: (Eq a) => [a] -> [a] -> [a]
setDifference xs excludes = filter (not . (elem excludes)) xs


Test:

*Main> setDifference [1,2,3] [2,4,5,6]
[1,3]


I find that to be a very succinct, readable definition. I probably would have written it too. Unfortunately it's wrong!

One of the more tedious requirements of beautiful code is that it be correct, so let's set up some really quick testing using QuickCheck. Since you've been reimplementing functions from base QuickCheck can generate a bunch of random test data and throw it at both the original function and your reimplementation and verify that the outputs match.

We'll start by defining a property that says the output from setDifference and \\ should always be the same.

prop_equal :: (Eq a) => [a] -> [a] -> Bool
prop_equal xs ys = setDifference xs ys == xs \\ ys


We can use this property ourselves in an interactive session, but that gets tedious fast. Instead, call quickCheck with the property and it will generate arbitrary data to test it with.

GHCi

> :m +Test.QuickCheck
> quickCheck prop_equal
*** Failed! Falsifiable (after 9 tests and 4 shrinks):
[(),(),(),(),(),()]
[()]


Aha! QuickCheck has determined that our property doesn't always hold. Each line printed after "Failed!" corresponds to an argument to the property. This might appear a little confusing due to the use of () (the unit or void type). Because our property was polymorphic, GHC picked a default. You can specialize the property to get output with other types, try quickCheck (prop_equal :: String -> String -> Bool). (You may have gotten slightly different output, that is okay and expected due to the generation of arbitrary data having been random.)

By itself this might not tell us enough though, why did these two arguments produce a failure? You can get all of the cases that QuickCheck tried by using verboseCheck instead.

GHCi

> verboseCheck (prop_equal :: String -> String -> Bool)
... pages ...


This will print a whole pile of text with various passing and failing cases until it gives up trying to shrink the test case. Run verboseCheck a couple of times and eyeball the output, you should be able to notice that it always reduces the failure to something like the following.

Passed:
"aa"
"b"
Failed:
"aa"
"a"


If you explore these examples manually in the repl or simulate them by hand (or imagination) you'll see that setDifference removes every instance of the elements from excludes from xs instead of just the first as \\ does. Now armed with the fact that the implementation is wrong, and knowing what's wrong with it we can head back to the drawing board to fix setDifference.

For a full exploration of QuickCheck check out Real World Haskell's chapter on QuickCheck.

• A useful idiom for dealing with the ambiguous/defaulted types issue without having to specify a complete type signature is to define a tuple with type annotations in a where clause, e.g. where _types = (xs :: String, ...). (The underscore prefix ensures GHC won't generate a unused variable warning) – hammar May 15 '14 at 9:10