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

On Fri, Jun 25, 2010 at 12:58 AM, Ivan Miljenovic wrote:

On 25 June 2010 14:41, David Menendez wrote:

...

On Thu, Jun 24, 2010 at 3:08 AM, Ivan Miljenovic 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 http://www.eyrie.org/~zednenem/