[Haskell-cafe] Type vs TypeClass duality

[Jules Bean]

Short answer: You are worrying about syntax. The things you want are 
possible.

TJ wrote:
> Following up on my previous thread, I have figured out why it bothered
> me that we cannot have a list such as the following: ["abc", 123, (1,
> 2)] :: Show a => [a]

That type doesn't mean what you want it to mean. That means :

A list of objects of some fixed type 'a', such that a is a member of the 
typeclass 'Show'. In fact, "worse" than that, it's a polymorphic list, 
which means the *caller* should be able to choose the type 'a'.

What you want to mean is 'A list of objects, each of which is of some 
possibly different type 'a', subject only to the restriction that a is a 
member of typeclass Show.

> It seems to me that there is an annoying duality in treating simple
> algebraic data type vs type classes. As it stands, I can only have a
> list where all the elements are of the same basic, ADT, type. There is
> no way to express directly a list where all the elements satisfy a
> given type class constraint.

There is, it's just not as simple as you want it to be. You need a 
constructor for the existential, as shown in the recent Renderable thread.

Incidentally there is no restriction that all the elements in a list 
have to be an ADT. They can be functions, or tuples of functions, or 
higher order functions, or lists of tuples of higher order polymorphic 
functions operating on lists of functions on tuples of.....

In GHC they can even be higher-rank.

> 
> If I am not mistaken, type classes are currently implemented in GHC like so:

[You are pretty much right, but of course how type classes are 
*implemented* isn't relevant, except as intuition. Any proposed 
extension should be based on what they mean (their semantics) not how 
GHC does it]

> Suppose that I have a list of type Show a => [a], I imagine that it
> would not be particularly difficult to have GHC insert a hidden item
> along with each value I cons onto the list, in effect making the
> concrete type of the list [(Dictionary Show, a)].

Right. That's almost exactly what the Showable existential does.

 > I'm assuming that it
> will not be particularly difficult because GHC will know the types of
> the values I cons onto it, so it will most definitely be able to find
> the Show dictionary implemented by that type, or report a type
> mismatch error. No dynamic type information is necessary.

Now it sounds like your only complaint is that : has the wrong type?

You could have a special case of (:) with type

(:) :: Show a => a -> [Showable] -> [Showable]

and then you could write:

"123" : 34 : "foo" : [1,2,3] : (1,2,3) : []

> I am not an OO programming zealot, but I'd like to note here that this
> is also how (class based) OO languages would allow the programmer to
> mix types. e.g. I can have a List<Show> where the elements can be
> instances of Show, or instances of subclasses of Show.
> 
> Why does this second rate treatment of type classes exist in Haskell?

I don't think it is second rate :)

Type classes are a different thing from types, of course they are 
treated differently...

Or maybe, if you're asking a slightly different question:

"Why is there always some syntactic hint, like an explicit constructor 
or a carefully typed combinator, when existentials come into play?"

then the answer is "because of type inference".

That is, the type inference algorithm which GHC uses, which is not the 
only one you can imagine, but for a variety of reasons is considered to 
be one of the best choices, cannot 'automatically' construct 
existentials, and requires some kinds of explicit annotations to 
'delimit' the existential.

I will also repeat the non-justified assertion that others have made, 
and that I've made myself in the other thread, that you don't need 
existentials as often in haskell as you do in OO languages, and they 
certainly don't always need to be type-class quantified ones.

Jules