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

On 07/04/2009, Ryan Ingram wrote:

On Mon, Apr 6, 2009 at 2:36 PM, Peter Berry 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 Please avoid sending me Word or PowerPoint attachments. See http://www.gnu.org/philosophy/no-word-attachments.html