[Haskell-cafe] Can we do better than duplicate APIs?

[Benjamin Franksen]

Simon Peyton-Jones wrote:
> | One reason why I think type classes have not (yet) been used to reduce
the
> | amount of API repetition is that Haskell doesn't (directly) support
> | abstraction over type constraints nor over the number of type parameters
> | (polykinded types?). Often such 'almost equal' module APIs differ in
> | exactly these aspects, i.e. one has an additional type parameter, while
yet
> | another one needs slightly different or additional constraints on
certain
> | types.
> 
> Interesting observation. Can you give a few examples in support of it?

For a start, the package compact-string that motivated my message: same
interface as Data.ByteString (apart from functions added for en/decoding),
only an extra type variable 'a' plus an 'Encoding a' constraint. Then there
is the notorious Ord constraint on the elements of a Data.Set (which e.g.
forbids making Set an instance of Monad) and for the keys in Data.Map. The
latter has one additional type parameter for the keys; otherwise the
interface of Set could share a lot with the one for Map. Probably the best
illustration is the function filter (which is listed in the ghc6.6 library
docs for no less than 9 different modules; 4 times in
compact-string). Here are some of them

Data.Set:

 filter :: Ord a => (a -> Bool) -> Set a -> Set a

Data.Map:

 filter :: Ord k => (a -> Bool) -> Map k a -> Map k a

Data.List:

 filter :: (a -> Bool) -> [a] -> [a]

and now Data.CompactString:

 filter :: Encoding a => (Char -> Bool) -> CompactString a -> CompactString
a

After taking another look at J.P.Bernardy's collection library, I see now
that all these (apart from the compact-string ones) have indeed been
subsumed under a single type class -- albeit using MPTCs, FunDeps, and
undecidable instances, of which at least the last one is most probably not
going to be standardized for Haskell' (and for good reasons, I suppose ;-).
I /do/ hope that the 'indexed types' aproach will make writing (and
understanding) such class frameworks a bit easier.

In this collections library there lives a copy of class Foldable, adapted to
a MPTC/FunDep framework, c.f.

Data.Collections.Foldable:

 class Foldable t a | t -> a where...

Data.Foldable

 class Foldable t where...

The former allows an

 instance Foldable IntSet Int

which the former doesn't, because IntSet has the wrong kind.

> | Or maybe we have come to the point where Haskell's lack of a 'real'
module
> | system, like e.g. in SML, actually starts to hurt?
> 
> Great though ML modules are, it's not clear to me how they help in this
case.  Can you illustrate how the repetition could be avoided if you had ML
modules?

The context in which I placed this question might have been a bit
misleading. I don't know ML enough to have an opinion as to whether its
module system makes it any easier to abstract over (the ML equivalent (if
there is one) of) type constraints or over additional type variables.

What I meant is that in ML you may give separate definitions for interfaces
('signatures') and implementations ('structures'). The main advantage is
that I write the types (and documentation!) in /one/ place, the signature,
and the compiler checks whether a given structure conforms (type-wise) to a
given signature. And the user, too, has /one/ place to look for types and
documentation. That doesn't free anyone writing a new implementation from
doing just that, and there will doubtless be some duplication involved if
the functionality is very similar. However, this could be hidden in the
implementation. From the outside it's just another module implementing some
general and well known interface (at least that is how I imagine things
should be).

Haskell's control-the-namespace-only approach to modules is nice because it
makes the module system very easy to understand and use; and it separates
the concerns of controlling the namespace from the (arguably) orthogonal
concern of (hierarchical) interface design. I even agree that temporarily
ignoring the latter, i.e. the strategy "let's get implementations first,
design the structured framework later" makes sense, but only up to a
certain point, which I think is approaching rapidly. (And which is the main
point I was trying to make.) BTW, I regard the Foldable and Traversable
interfaces as an extremely valuable step in the right direction. They also
showed me how much (more) insight is necessary to find the right
abstractions.

Cheers
Ben