[Haskell-cafe] Fwd: Re: Overlapping instances

[David Feuer]

Oddly, this message was rejected by the system. Trying again.
---------- Forwarded message ----------
From: "David Feuer" <david.feuer at gmail.com>
Date: Feb 24, 2016 10:04 PM
Subject: Re: [Haskell-cafe] Overlapping instances
To: "Mitchell Rosen" <mitchellwrosen at gmail.com>
Cc: "Haskell-cafe" <haskell-cafe at googlegroups.com>

It's possible that GHC will backtrack with overlapping enabled (I can't
remember, and overlapping instances give me hives) but it doesn't have
here. The first instance is "more specific" than the second because the
type variable x appears twice.
On Feb 24, 2016 9:49 PM, "Mitchell Rosen" <mitchellwrosen at gmail.com> wrote:

> Consider this "list membership" typeclass and two overlapping instances:
>
> class Elem (x :: k) (xs :: [k])
>
> instance {-# OVERLAPS #-} Elem x (x ': xs)
> instance {-# OVERLAPS #-} Elem x xs => Elem x (y ': xs)
>
> The inductive style is satisfying, but I'm struggling to understand
> exactly how GHC can pick one instance over the other.
>
> How is a constraint like Elem Int [Int] solved? Certainly the Elem x (x
> ': xs) instance matches, with x = Int and xs = []. But, the second
> instance is also equally valid with x = Int, y = Int, xs = []. Even
> though *if *the second instance is chosen, the context cannot be
> satisfied (no instance for Elem x []), it's my understanding that GHC
> will not backtrack once it picks an instance. And because both instances
> look valid to me, I don't understand why this code does not require
> IncoherentInstances.
>
> Thanks.
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20160224/3f3f7678/attachment.html>