[Haskell-cafe] Fwd: signficant improvements to the containers package

[Ivan Miljenovic]

On 24 June 2010 17:55, Stephen Tetley <stephen.tetley at gmail.com> wrote:
> On 24 June 2010 08:20, Ivan Miljenovic <ivan.miljenovic at gmail.com> wrote:
>
>> My rational for a class approach is that rather than having your
>> library spit out a list of values, etc. you let the consumer pick
>> which data type they prefer (if they're going to be just converting
>> your list into a Set, then why not give them a Set to start with?).
>>
>
> That's a bit more interesting, at least to my tastes.
>
> In my own work I often use specialised container types: e.g. rather
> than use a 'safe list' library that avoids certain list ops or wraps
> them as Maybe's, I prefer using a OneList:
>
> data OneList a = One a | Cons a (OneList a)

Hmmm.....

/me makes a note to see whether or not having an empty value is a
requirement of such classes...

> With structures like a OneList their construction is more 'primary'
> than their manipulation. That's to say clearly when you build a
> OneList it can't be empty (and you obviously don't want it to be), but
> as a structure its not conducive to many manipulations, e.g: you can't
> filter it, as filtering can produce an empty list but the data type
> can't.

Yeah, which can be a problem.

> Some "algebra" of constructors and destructors would be useful here,
> to get the filterInto function for example:
>
> filterInto :: Consable c => (a -> Bool) -> OneList a -> c a
>
> Consable could be the Coll class from "Bulk Types with Class" or
> probably better, a smaller one with just empty and cons, or even just
> cons inheriting Monoid. Unfortunately inheriting Monoid puts
> "legitimacy" on (++) which we know is bad on regular lists, and should
> discouraged where feasible. Similarly size in the Coll class is bad on
> regular lists... it goes on until will have single operation type
> classes for all the collection operations.

If you inherit Monoid, then Bytestring can't be an instance of the class...

This dichotomy is a problem: we'd like to have as many possible types
be instances of such classes as possible; however, if we do that then
we can't use pre-existing classes such as Functor since Set isn't an
instance of Functor, etc.

Anyway, since I've brought the whole thing up now rather than in the
blog post I was planning to write this weekend, what are people's
thoughts on preferred extension used:

* MPTCs + fundeps

Pros: older tech, more widely understood/used, ListLike already uses it

Cons: I don't like the fact that the element type becomes a "first
class member" of the type class; I'd prefer writing "SetLike s =>
Value s -> s -> s" to "SetLike s v => v -> s -> s" as IMHO the class
represents the data type/structure and not the value it stores (that's
a sub-part).

* Type Families (actually using an Associated Type)

Pros: IMHO cleaner type sigs (see above), in "Fun with Type Families",
the authors call Type Families more like functional programming
whereas fundeps are more like logic programming, and also state that
type families play nicer with GADTs, etc.

Cons: newer tech, so still being developed and used, etc.  In
particular, superclass constraints are not yet implemented in GHC
(i.e. can't say something like "class (SetLike l, Value l ~ (k, v)) =>
MapLike l where ..."

Unlike the choice of which gets used in FGL, I would like to think
that this kind of set of classes would be more widely used in the
community and will use whichever type of extension seems to be
consensus as the better one (at least for this situation).  If anyone
knows a good site to be able to make an actual poll for this, that
would probably be even better (or should we just have a wiki page
where people put their names under whichever they think is better and
then just tally up the number of names for each?).

-- 
Ivan Lazar Miljenovic
Ivan.Miljenovic at gmail.com
IvanMiljenovic.wordpress.com