Containers in the Haskell Platform

[Johan Tibell]

Hi Alex,

On Thu, Aug 6, 2009 at 9:15 AM, Alexander
Dunlap<alexander.dunlap at gmail.com> wrote:
> The way I see it, we have a few options. We could introduce some type
> classes to cover the various container operations and ask all Platform
> packages to only use operations from these classes, where applicable.
> (The ListLike library would probably be a good place to start.) The
> issue here is efficiency, massive class dictionaries, and type system
> issues (we need MPTCs or TFs; also, since not all sequence types are
> polymorphic, we probably need to have separate map and rigidMap
> functions like in ListLike, and even that doesn't work for types like
> uvector that can take some, but not all, concrete element types).

I don't like the *Like naming much. I think that the type class
deserves the shorter name and concrete instantiations should use more
specialized names. Sequence wouldn't be a too bad name for data types
that support indexing. Stream would be a good name for types that
don't. There's an issue with regards to monads though. What type
classes do we use for a Stream backed by e.g. an I/O resource? Example
using a concrete element type:

class ByteStream s where
    uncons :: s -> (Word8, s)
    null :: s -> Bool

class ByteStreamM s where
    uncons :: Monad m => s -> m (Word8, s)
    null :: Monad m => s -> m Bool

Do we need two type classes for each "concept" (e.g. stream, sequence)?

> We could also implement a standard module-naming scheme: for every
> package that operates on strings, for instance, we could require the
> list-based code to go in Foo.Bar.String and the Text code to go in
> Foo.Bar.Text. Whenever we "blessed" a new string datatype (presumably
> not very often), all packages would have to add a new module. The
> issue is code duplication.

I would like to propose this as a general recommendation for module
naming as there's already plenty of modules that do it this way. It
also seems to be the most sensible place to put the data type as it
groups related modules in the module hierarchy and thus in the
documentation. I don't know about requiring all packages to add a new
module every time there's a new type though.

>
> We could also implement a package naming scheme: have foo-text and
> foo-string for the two different datatypes.

This seems like a good scheme to me. It's the same
<general>-<specific> scheme that's proposed for modules above.

>
> What does everyone think about the need for standardization here and
> how we ought to do it? I'm sorry that, having less experience with
> Haskell than many, I can't give as much in the way of concrete
> proposals, but I think it's important that we hash something out here
> to get more organization in our Platform.

I definitely think the container problem needs to be tackled. However,
I don't know what the solution should look like.

Cheers,

Johan