Collections (was: Arrays)

[Robert Dockins]

On Mar 2, 2006, at 1:57 PM, Alson Kemp wrote:

>> This doesn't address Bags, Heaps, Finite Relations
>> or 'cons'able
>> sequences.
> True.
>
> Perhaps my listing was incomplete, in which case this
> might fix it:
>>>   Collection
>>>    .Array
> * *    .Bag
> * *    .FiniteRelations  -- Maps?

Finite Relations are to Finite Maps as Bags are to Sets.  Each key  
can be associated with multiple elements.

> * *    .Heap
>>>    .Map
>>>    .Set
>>>    .Tree
>>>      .Binary
>>>      .Rose
>>>   Data
>>>    . ...
>>>    . Int
>>>    . ...
>
> What is an example of a cons-able sequence? (aside
> from [])

See http://www.eecs.tufts.edu/~rdocki01/docs/edison/index.html

Edison contains about 8 or 9 different concrete implementations of  
sequences with varying time complexity for the core operations.


> Or, perhaps as a non-math-geared programmer, I've
> missed something.  I come at this from "make Haskell
> more useful to more programmers" rather than from
> "make Haskell a mathematically beautiful language" (I
> slept through Discrete Mathematics).  That said, if
> you can point me towards a paper, I'd be happy to read
> up and try to encompass the "mathematically beautiful"
> perspective, too.  (Especially since the proposal will
> probably get rejected without a component of
> mathematical beauty!  ;) )

I don't know of any papers of the top of my head.  I guess I just  
wanted to point out that the landscape of abstract data structures is  
wider than "Array, Set, Map".



Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG