[Haskell-cafe] Strange type error with associated type synonyms

[Peter Berry]

On 07/04/2009, Ryan Ingram <ryani.spam at gmail.com> wrote:
> On Mon, Apr 6, 2009 at 2:36 PM, Peter Berry <pwberry at gmail.com> wrote:
>> As I understand it, the type checker's thought process should be along
>> these lines:
>>
>> 1) the type signature dictates that x has type Memo d a.
>> 2) appl has type Memo d1 a -> d1 -> a for some d1.
>> 3) we apply appl to x, so Memo d1 a = Memo d a. unify d = d1
>
> This isn't true, though, and for similar reasons why you can't declare
> a generic "instance Fun d => Functor (Memo d)".  Type synonyms are not
> injective; you can have two instances that point at the same type:

Doh! I'm too used to interpreting words like "Memo" with an initial
capital as constructors, which are injective, when it's really a
function, which need not be.

> You can use a data family instead, and then you get the property you
> want; if you make Memo a data family, then Memo d1 = Memo d2 does
> indeed give you d1 = d2.

I'm now using Data.MemoTrie, which indeed uses data families, instead
of a home-brewed solution, and now GHC accepts the type signature. In
fact, it already has a Functor instance, so funmap is redundant.

-- 
Peter Berry <pwberry at gmail.com>
Please avoid sending me Word or PowerPoint attachments.
See http://www.gnu.org/philosophy/no-word-attachments.html