Implying equality in a Haskell pattern match

11
votes

I'm writing a function to simplify a Boolean expression. For example, Nand(A, A) == Not(A). I've tried to implement this particular rule using pattern matching, like so:

-- Operands equivalent - simplify!
simplify (Nand q q) = Not (simplify q)
-- Operands must be different, so recurse.
simplify (Nand q q') = Nand (simplify q) (simplify q')

Upon compiling, I get the error:

Conflicting definitions for `q'
Bound at: boolean.hs:73:21
          boolean:73:29
In an equation for `simplify'

I think I understand what's going on, and I've worked around it, but I'd just like to know:

  1. Why is this sort of pattern matching not possible?
  2. Is there an idiomatic workaround?

Full disclosure: this is related to homework, but the purpose of the course is not to learn Haskell, and I've solved it my own way anyway.

3
haskellpattern-matchingboolean-logic
A pattern that uses a variable twice is called a non-linear pattern. There are languages that provide non-linear patterns like Erlang and I think it was a design choice to not include them in Haskell. The mailing list post mail-archive.com/[email protected]/msg03721.html contains some arguments against non-linear patterns but they are quite high-level arguments. - Jan Christiansen
Note that (Nand q q') does not imply that q and q' are different. q = 3 q' = 3 (I think this is the reason for the design choise) - Viktor Mellgren
@Vixen, well, if the first pattern wouldn't match, it'd mean that they are different in the second pattern... - dflemstr
Yeah, I know, but I think that q not neccecarily == q' was the design descision behind it - Viktor Mellgren
@Vixen: noted! I changed the comment so it doesn't seem like (Nand q q') implies q /= q'. - Daniel Buckmaster

3 Answers

15
votes

The solution I've found is to use guards to check for equality of sub-structures:

simplify (Nand q q')
    -- Operands equivalent - simplify!
    | q == q' = Not (simplify q)
    -- Operands different - recurse.
    | otherwise = Nand (simplify q) (simplify q')
2
votes

You could stick to your original style:

-- Operands equivalent - simplify!
simplify (Nand q q') | q == q' = Not (simplify q)
-- Operands must be different, so recurse.
simplify (Nand q q') = Nand (simplify q) (simplify q')

Also, I think you should simplify before equality testing and not after:

simplify (Nand q q') = if qs == qs' then Not qs else Nand qs qs' where
    qs = simplify q
    qs' = simplify q'
1
votes

The "answer" is that you're not allowed to mention the same variable twice in a pattern. Not in Haskell, anyway. The best way to solve this is the one you appear to have already discovered - use pattern guards to test for equality or inequality.