[Haskell-cafe] Explicitly calling syntactic equality on datatypes

[Tom Ellis]

On Tue, Sep 17, 2019 at 02:56:36PM +0100, Juan Casanova wrote:
> data Sum = Value Int | Sum Sum Sum
[...]
> But then, I want to define equality semantically. An obvious way to go is to
> produce a function that normalizes Sums (from the first definition) to
> guarantee that the first sub-sum is always going to be a value, and then
> check that these two are "equal".
> 
> And this is where my question comes in, because, of course, the following is
> infinite recursion:
> 
> instance Eq Sum where a == b = (normalize a) == (normalize b)

Then why not introduce a datatype which guarantees structurally the that
value is normalised and use its Eq?

    data SumNormalised = ValueNormalised Int | SumNormalised Int Sum
        deriving Eq
    
    normalize :: Sum -> Sum Normalised
    normalize = <pretty much the same body you would have had before>

    instance Eq Sum where a == b = (==) `on` normalize

Tom