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

[David Menendez]

On Fri, Jun 25, 2010 at 12:58 AM, Ivan Miljenovic
<ivan.miljenovic at gmail.com> wrote:
> On 25 June 2010 14:41, David Menendez <dave at zednenem.com> wrote:
>> On Thu, Jun 24, 2010 at 3:08 AM, Ivan Miljenovic
>> <ivan.miljenovic at gmail.com> wrote:
>>> As an aside, Alex Mason and I are discussing the possibility of taking
>>> advantage of AusHack *shameless plug* to write some kind of classes
>>> for the different types of containers with a hierarchy.  I know about
>>> ListLike, but there doesn't seem to be any applicable classes for
>>> generic containers (i.e. the abstract API of a Set; something like
>>> ListLike would then be an extension on it) and for lookup data
>>> structures (Map k a, [(k, a)], etc.).
>>
>> Be sure to look into Okasaki's work on Edison. It has classes for
>> sequences (list-like structures) and collections (sets, heaps) and
>> associations (maps, priority queues) and a paper discussing the design
>> decisions.
>
> Yeah, we will be.
>
> The reason this came up: Thomas Berekneyi wanted to use such classes
> for the rewrite of FGL, and when he discussed it on #haskell people
> generally indicated that edison was the best out there but was a bit
> long in the tooth and something like it should be re-written (though
> no-one seemed to volunteer... hmmm... :p).

Edison could use some re-thinking; the state of the art in Haskell has
advanced, and there are new classes like Data.Foldable and
Data.Traversable to consider.

In my mind, the big question is whether Sequence and Assoc should be
constructor classes or use type families/fundeps. I lean towards the
former, but it means that things like ByteSting can't be instances of
Sequence.

> For example: it's a little weird that edison re-exports Data.Set and
> uses it for the instance with a type alias (same with map, Seq, etc.)
> rather than just using Data.Set itself.

I believe that's so the implementations export a common interface. If
you're in a situation where you want to use a specific implementation,
Edison is designed so that you can import just the implementation
module and avoid the overhead of the class system while still making
it easy to switch implementations in the future.

>  I also find the
> structuralInvariant and instanceName fields to be a little odd,

I believe structuralInvariant is there for testing.

I'm not sure what instanceName is for. It's possible Edison predates
Data.Typeable, in which case instanceName might be useful for similar
purposes.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>