CODEWITHSUNDEEP
haskell
Wireless
Wireless

Reputation: 107

Custom Eq Instance for Data Type

I'm having some issues getting to create my own Eq instance for my data type.

This is my code:

data Doc = Empty -- Adds ""
    | Text String
    | NewLine -- Adds "\n"
    | Concat Doc Doc -- Joins two Doc's

instance (Eq Doc) => Eq (Doc) where
    Concat a1 b1 == Concat a2 b2 = True
    _ == _ = False

My objective is that it only returns True when the final Doc is the same, for example:

*Main> Concat (Concat (Text "The ") (Text "birds"))(Concat Empty NewLine) == Concat Empty (Text "The birds\n")

This should be True and with the code I have it does return True, but it's returning True every single time, even if I have totally different sentences.

I've been battling around with this for a while and searched around but came up with nothing. Any of you guys have any idea or suggestion as to what I'm doing wrong here?

Thanks in advance!

Upvotes: 1

Views: 611

Answers (2)

Rein Henrichs
Rein Henrichs

Reputation: 15605

There are two questions here, so let's take them in turn.

What's wrong with my definition?

You define any two Concat documents as equal, regardless of what they contain. You also define any other values as inequal, regardless of what they contain. This means that, for instance,

Concat (Text "foo") Newline == Concat (Text "bar") Newline

gives True, while

Text "foo" == Text "foo"

gives False.

Let's write a definition for structural equality instead: two Docs are equal if they have the same structure:

instance Eq Doc where
  -- Concats are equal if the things they are concat-ing are equal
  Concat a b == Concat a' b' = a == a' && b == b'
  -- Newlines are always equal
  NewLine = NewLine = True
   -- Two texts are equal if the text they contain is equal
  Text a = Text a' = a == a'
  -- Everything else is inequal
  _ = _ = False

How can I write an Eq instance that doesn't care about structure, only whether the generated documents are the same?

If we want to compare the generated documents, we can do just that:

instance Eq Doc where
  doc == doc' = generate doc == generate doc'

assuming that generate :: Doc -> String does what it says. We can also use on from Data.Function to write this as

(==) == (==) `on` generate

As William mentions in the comments, this "does not satisfy the equality constraints". However, there is precedent for this: the diagrams package considers two diagrams to be equivalent if they generate the same instructions for drawing a diagram. The reasoning behind this is explored in the paper introducing Diagrams:

The particularly attentive reader may have noticed something strange about this Semigroup instance: (<>) is not associative! d1 <> (d2 <> d3) and (d1 <> d2) <> d3 are not equal, since they result in trees of two different shapes. However, intuitively it seems that d1 <> (d2 <> d3) and (d1 <> d2) <> d3 are still “morally” the same, that is, they are two representations of “the same” diagram. We can formalize this idea by considering Diagram as a quotient type, using some equivalence relation other than structural equality. In particular, associativity does hold if we consider two diagrams d1 and d2 equivalent whenever unD d1 ≡ unD d2, where unD::Diagram → [Prim] “compiles” a Diagram into a flat list of primitives.

Upvotes: 4

Zeta
Zeta

Reputation: 105886

According to your code, any Concat will be equal to another Concat. Let's try to check the equality by hand:

Concat NewLine (Text "Huh") == Concat (Text "Example") (Text "Concat")
= True -- inserted definition of `==`

We never look at the elements of your Concat. But at some point we have to check that Newline == Text "Example" and return False. An important hint is that you never inspect a1, b1 and so on. As soon as we try to use them, the instance comes naturally:

instance Eq Doc where
  Concat a1 b1 == Concat a2 b2 = a1 == a2 && b1 == b2
  Text ...     == ...          = -- left as exercise
  Newline ...  == ...          = -- left as exercise
  _            == _            = False

Upvotes: 1

Related Questions