From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: weis
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA03706 for caml-redistribution; Wed, 19 Jan 2000 23:50:49 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA14426 for <caml-list@pauillac.inria.fr>; Wed, 19 Jan 2000 23:50:07 +0100 (MET)
Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35])
	by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id XAA23553;
	Wed, 19 Jan 2000 23:50:05 +0100 (MET)
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA25766; Wed, 19 Jan 2000 23:50:03 +0100 (MET)
From: Pierre Weis <Pierre.Weis@inria.fr>
Message-Id: <200001192250.XAA25766@pauillac.inria.fr>
Subject: Re: Compiler translation of array indexing
To: simonpj@microsoft.com (Simon Peyton-Jones)
Date: Wed, 19 Jan 2000 23:50:03 +0100 (MET)
Cc: caml-list@inria.fr
In-Reply-To: <7CD674FF54FBD21181D800805F57CD54821B89@RED-MSG-44> from "Simon Peyton-Jones" at Jan 19, 0 09:33:27 am
X-Mailer: ELM [version 2.4 PL24 ME8]
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: weis

> It's perhaps worth mentioning that one way of achieving
> this effect is to use type-driven overloading, as Haskell
> does.  One could say
> 
> 	class Array a where
> 	  (.) :: a elt -> Int -> elt
> 	  ... more operations...
> 
> (Here 'a' is a type variable ranging over type constructors
> of kind *->*.)

Thank you for the interesting information about Haskell.

As you suggested by your sketch program, the Haskell type classes are
undoubtedly a powerful and complex mechanism. 
However, it has some strange limitations that always seems extremely
``bizarre'' to me: for instance you may think you have a polymorphic
equality but this polymorphic equality cannot compare two polymorphic
objects (e.g. [] == [] is ill-typed). Strange, isn't it ?

For the example we are examining, I'm afraid that once more this
cannot be handled as desired by the Haskell type classes. In effect,
what we want in the first place (at least in Caml) is to get rid of
the two different syntactic notations for string and array accesses
(When we can do so, we can start to dream to an extension of the
mechanism to arbitrary vectors like data types).

Unfortunately, to the best of my knowledge, even if Haskell classes
can afford a zillion of instances of (.) for fancy vectors data types,
they just fail to handle the overloading of v.(0) and s.[0]: you
cannot declare string to belong to the class ``Array'' (since as you
carefully told us 'a' must have kind *->*, which is not the kind of
the string data type).

In the same vein, the next overloading I would want for .() would
certainly be for associative arrays (or hash tables in the Caml and
usual terminology). In this case, I want to declare that the (binary)
data type constructor ('a, 'b) hash_table as a member of the ``Array''
class. I don't think this is well-kinded.

Then, the following step would be to use the notation to access in lists.

To summerize, I really would like to write
 v.(1) instead of Array.get v 1
 s.(1) instead of String.get s 1

I would consider as an additional benefit of the new type system, if I
could use:
 t.("ok") instead of Hashtbl.find t "ok",
 l.("ok") instead of List.assoc "ok" l.

Unfortunately, I don't think that Haskell classes can handle the first
group, neither the second one; it just allows a strange mixture of the
two, since only the first and the last example can be declared as
member of the same class (and this would define list as a member of
``Array''!). Strange, isn't it ?

However, I just read the inference rules of the Haskell class system,
to figure out how overloading was resolved (tricky isn't it?). So I
never got an intuition of the class abstraction. So please, correct me
if I made false inferences about the class system.

In addition, since you are a true specialist of Haskell type classes,
may be you could tell us if there is some secret feature that you know
of in the Haskell type classes system that could elegantly deal with
these simple, useful, and natural examples ?

Sincerely,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/