Is it possible to debug pattern matching in a Haskell function?

Question

I have defined a type

data Expr = 
    Const Double
    | Add Expr Expr
    | Sub Expr Expr

and declared it as an instance of Eq typeclass:

instance Eq Expr where
    (Add (Const a1) (Const a2)) == Const b = a1+a2 == b
    (Add (Const a1) (Const a2)) == (Add (Const b1) (Const b2)) = a1+a2 == b1 + b2

Of course, the evaluation of the expression Sub (Const 1) (Const 1) == Const 0 will fail. How can I debug at runtime the pattern matching process to spot that it's failing? I would like to see how Haskell takes the arguments of == and walks through the patterns. Is it possible at all?

Answer 1

edit: providing a real answer to the question...

I find the easiest way to see what patterns are matching is to add trace statements, like so:

import Debug.Trace

instance Eq Expr where
    (Add (Const a1) (Const a2)) == Const b = trace "Expr Eq pat 1" $ a1+a2 == b
    (Add (Const a1) (Const a2)) == (Add (Const b1) (Const b2)) = trace "Expr Eq pat 2" $ a1+a2 == b1 + b2
    -- catch any unmatched patterns
    l == r = error $ "Expr Eq failed pattern match. \n l: " ++ show l ++ "\n r: " ++ show r

If you don't include a final statement to catch any otherwise unmatched patterns, you'll get a runtime exception, but I find it's more useful to see what data you're getting. Then it's usually simple to see why it doesn't match the previous patterns.

Of course you don't want to leave this in production code. I only insert traces as necessary then remove them when I've finished. You could also use CPP to leave them out of production builds.

I also want to say that I think pattern matching is the wrong way to go about this. You'll end up with a combinatorial explosion in the number of patterns, which quickly grows unmanageable. If you want to make a Float instance for Expr for example, you'll need several more primitive constructors.

Instead, you presumably have an interpreter function interpret :: Expr -> Double, or at least could write one. Then you can define

instance Eq Expr where
  l == r = interpret l == interpret r

By pattern matching, you're essentially re-writing your interpret function in the Eq instance. If you want to make an Ord instance, you'll end up re-writing the interpret function yet again.

Answer 2

If you wish to get some examples on how the matching may fail, you could have a look at QuickCheck. There's an example on the manual (the size of test data) about generating and testing recursive data types that seems to perfectly suit your needs.

While the -Wall flag gives you a list of patterns non matched, a run of QuickCheck gives you examples of input data that lead your given proposition to failure. For example, if I write a generator for your Expr and I give in input to quickCheck a proposition prop_expr_eq :: Expr -> Bool that checks if an Expr is equal to itself, I obtain very quickly Const 0.0 as a first example of non-matching input.

import Test.QuickCheck
import Control.Monad

data Expr = 
    Const Double
    | Add Expr Expr
    | Sub Expr Expr
    deriving (Show)

instance Eq Expr where
    (Add (Const a1) (Const a2)) == Const b = a1+a2 == b
    (Add (Const a1) (Const a2)) == (Add (Const b1) (Const b2)) = a1+a2 == b1 + b2

instance Arbitrary Expr where
    arbitrary = sized expr'
      where
        expr' 0 = liftM Const arbitrary
        expr' n | n > 0 = 
            let subexpr = expr' (n `div` 2)
            in oneof [liftM Const arbitrary,
                      liftM2 Add subexpr subexpr,
                      liftM2 Sub subexpr subexpr]

prop_expr_eq :: Expr -> Bool
prop_expr_eq e = e == e

As you see, running the test gives you a counterexample to prove that your equality test is wrong. I know this may be a little bit an overkill, but the advantage if you write things good is that you also get unit tests for your code that look at arbitrary properties, not only pattern matching exhaustiveness.

*Main> quickCheck prop_expr_eq
*** Failed! Exception: 'test.hs:(11,5)-(12,81): Non-exhaustive patterns in function ==' (after 1 test):  
Const 0.0

PS: Another good reading about unit testing with QuickCheck is in the free book real world haskell.

Answer 3

You can break your complex pattern into simpler patterns and use trace to see what's going on. Something like this:

instance Eq Expr where
    x1 == x2 | trace ("Top level: " ++ show (x, y1)) True,
               Add x11 x12 <- x1,
               trace ("First argument Add: " ++ show (x11, x12)) True,
               Const a1 <- x11,
               trace ("Matched first Const: " ++ show a1) True,
               Const a2 <- x12,
               trace ("Matched second Const: " ++ show a2) True,
               Const b <- x2
               trace ("Second argument Const: " ++ show b) True
             = a1+a2 == b

It's a bit desperate, but desperate times calls for desperate measures. :) As you get used to Haskell you rarely, if ever, need to do this.