[Haskell-cafe] Selecting Array type

[Ryan Ingram]

On 2/21/08, Jeff φ <jeff1.61803 at gmail.com> wrote:
> Thanks again.  I'm not familiar with type equality constraints.  I could not
> find information on this in the GHC users guide.  Is it documented
> somewhere?

Section 7.3 here talks about equality constraints.
http://www.haskell.org/haskellwiki/GHC/Indexed_types

There's an extremely good paper talking about the low-level mechanisms
for equality constraints in GHC Core here:
http://research.microsoft.com/%7Esimonpj/papers/ext%2Df/

GHC Core -is- System Fc as described in that paper; the type equality
constraints amount to a "coercion" function that is passed around the
core language to convert between the types and which is statically
guaranteed to be the identity function.

> It is interesting that you were able to drop the IArray
> constraint from the instances of SmartArraySelector.

During compilation from Haskell to Core, the compiler implicitly adds
calls to any available conversion functions it knows about as required
to convert between types.  This is why the IArray declaration can be
dropped; the compiler looks at the coercions currently available,
finds (a ~ UArray), and inserts a call that converts the existing
"IArray UArray Bool" declaration into an "IArray a Bool" declaration.
Determining that such a path exists is a search problem and much of
the work with associated types and type equality constraints involves
proving that the search is decidable.

  -- ryan