Haskell pattern-matching idiom

Question

I'm making a calculator on abstract integers and I'm doing an awful lot of pattern matching. I can write

add Zero x  = x
add (P x) y = next $ add (prev $ P x) y
add (N x) y = prev $ add (next $ N x) y

or

add Zero x  = x
add x y = case x of
    P _ -> next $ add (prev x) y
    _   -> prev $ add (next x) y

While the first way is shorter, something in the second way appeals to me more.

Which is the preferred way to do this?

`prev` looks like `prev (N x) = x; prev x = P x` but then shouldn't it be `add (P x) y = prev $ add x y`? — Gurkenglas, Dec 10 '16 at 12:32
Actually it's much more complicated than that; I have `data AbInt = Zero | P Nat | N Nat` where `data Nat = One | S Nat`, simulated positive and negative with `P` and `S` wrappers respectively, so `prev (N x) = N $ S x` and so on. — , Dec 10 '16 at 12:42
You might want to consider including zero as a natural number using `data Nat = Zero | S Nat`. This allows a slightly more opaque, but much easier to work with, definition of `data Int' = Z Nat Nat`, since you no longer need to distinguish between positive, negative, and zero integers explicitly. For instance, `next (Z a b) = Z (S a) b` and `prev (Z a b) = Z a (S b)`. Even better, `intAdd (Z a b) (Z x y) = Z (natAdd a x) (natAdd b y)` for suitably defined `natAdd :: Nat -> Nat -> Nat`. — chepner, Dec 10 '16 at 15:45

score 3 · Accepted Answer · edited May 23 '17 at 12:32

3

Use as-patterns.

add Zero y = y
add x@(P _) y = next $ add (prev x) y
add x@(N _) y = prev $ add (next x) y

I'd also consider abstracting out the common structure of your two recursive branches by noting that you just swap the roles of the prev and next functions depending on whether x is positive or negative:

add Zero x = x
add x y = f $ add (g x) y
    where (f, g) = case x of
                       P _ -> (next, prev)
                       N _ -> (prev, next)

edited May 23 '17 at 12:32

Community

1
1

answered Dec 10 '16 at 12:32

Benjamin Hodgson

42,952
15
108
157

That second option is very interesting, and something I totally hadn't considered. (Well, I hadn't considered the first, either, but I didn't know about it.) In your mind, is the conceptual clarity there worth the extra two lines? – Dec 10 '16 at 12:48
@Canyon I don't think it particularly matters. The second implementation does emphasise that adding negative numbers is "the opposite" of adding positive numbers, especially if you can come up with better names than `f` and `g`. But the duplication in the first implementation isn't _too_ egregious, because it's only two lines and they're right next to each other – Benjamin Hodgson Dec 10 '16 at 13:00

score 1 · Answer 2 · answered Dec 10 '16 at 13:43

About this style:

add Zero x  = x
add x y = case x of
    P _ -> next $ add (prev x) y
    _   -> prev $ add (next x) y

On the positive side, it avoids some repetition, which is good.

On the negative side, the case looks to be non-exhaustive at a first sight. Indeed, to convince oneself that the pattern match is really exhaustive, we have to reason about the possible values for the x in case x of, and see that at runtime that can not be Zero, because that was handled above. This requires far more mental effort than the first snippet, which is obviously exhaustive.

Worse, when turning on warnings, as we should always do, GHC complains since it is not convinced that the case is exhaustive.

Personally, I wish the designers of Haskell had forbidden non exhaustive matches entirely. I'd use a -Werror-on-non-exhaustive-matches if there were one. I would like to be forced to write e.g.

case something of
   A -> ...
   B -> ...
   _ -> error "the impossible happened"

than having the last branch being silently inserted by the compiler for me.

@luqui Yes, that's true. I usually compile with `-Wall`, though, and I find `-Wall -Werror` to be overkill. — chi, Dec 11 '16 at 15:06

Daniel Wagner · Answer 3 · 2016-12-11T03:32:10.540

Consider using the math-style definition of integers as congruence classes of pairs of naturals under the equivalence relation:

{((a,b), (c,d)) | b+c == d+a}

The intuition is that the pair of naturals (a,b) represents b-a. As mentioned in the Wikipedia article, this often reduces the number of special cases compared to the "0/positive/negative" definition. In particular, the addition operation you ask about implementing becomes a one-liner:

-- both Int and Integer are taken
data Int' = Int Nat Nat

instance Num Int' where
    -- b-a + d-c = (b+d)-(a+c)
    Int a b + Int c d = Int (a + c) (b + d)

It's kind of fun to work through the different operations with this representation. For example, Eq can be implemented with the equation given above, and Ord is similar:

instance Eq Int' where
    -- b-a == d-c = b+c == d+a
    Int a b == Int c d = b+c == d+a

instance Ord Int' where
    -- compare (b-a) (d-c) = compare (b+c) (d+a)
    compare (Int a b) (Int c d) = compare (b+c) (d+a)

On occasion, it can be handy to normalize these things. Just like fractions can be reduced by multiplying the numerator and denominator by the same number until they're relatively prime, these things can be reduced by adding or subtracting the same number to both parts until (at least) one of them is zero.

normalize (Int (S a) (S b)) = normalize (Int a b)
normalize v = v

Haskell pattern-matching idiom

3 Answers3