Re: new contributed library: <treap>

[Jonathan Bachrach <jrb@xxxxxxxxxx>]

Neel Krishnaswami <neelk@alum.mit.edu> writes:

> Hi all,
> 
> I wrote a new collection class in goo, and stuck it on the wiki (under
> GooLibs). I'll blurb it a little, so you know what I'm talking about,
> and then write about what I found easy/hard about the experience.
> 
> o <treap> is a new mapping class that implements purely functional
>   balanced binary trees.

for all ya twistedmatrix peops out there, i think you should rename it
<trp>.  hehe.  don't want to crack ya mama's back, now do ya?

> ...
> Comments on writing it:
> 
> I picked a functional map to slightly push the goo collection
> protocol a little, since it's a kind of collection that the protocol
> hadn't been designed in mind with.  Overall, the experience was
> fairly straightforward, once jrb diagnosed that you have to
> implement the enumeration protocol before anything else.
> 
> o That's probably symptomatic of my main difficulty: it's not clear
>   which methods I must override in order to have a collection that
>   works reliably with all the collection methods. 

i would very much like some sort of interface mechanism.  back in the
day, we definitely had an idea that this could be implemented merely
in terms of dylan's abstract classes and generics.

>   It would be really great if there were a 'Collection-writing 101'
>   document that described exactly which methods need to get
>   overridden. 

i'll do it.

>   Restarting goo again and again as methods called each other
>   without a terminating base case and crashed goo was not so much
>   fun.

yes, there needs to be a stack overflow check.

>   I'm still not sure I have a complete set of collection methods,
>   actually. I'm sure that the set is *small*; I'm just not sure
>   I got it all. (col was a last-minute addition, for example.)

`col' shouldn't be necessary.  i'll investigate.

> o I had a similar problem with the exception system: I wasn't
>   sure which exceptions to throw where, so I just used an (error
>   "foo") everywhere. This is rather suboptimal, because it really
>   degrades the value of the exception system for library users.
> 
>   Python is a good model here. It has a fine-grained, well-documented
>   exception hierarchy, and the std library makes use of it
>   everywhere. 

i'm on the case.

> o There are a couple of missing functions from the protocol:
> 
>   add-key: (c|<map> key|<any> val|<any> => <map>)
> 
>    This is just the dual of del. 

i guess elt-setter wouldn't be appropriate here because it implies
side-effecting?  also this name is a bit misleading especially wrt to
sets.  why would it take a val?  perhaps it should be called `map-add'.

>   fold-map: (f|<fun> init|<any> c|<col> => <any>)
>     
>     This is (f (f (f (f init k0 v0) k1 v1) ...))
>     where ki/vi are key-value pairs.

ok, i'll add this.

>   do-map: (f|<fun> c|<col>)
>   
>    This calls (f k v) on each key/value pair for side-effect. 

that's called `do-keyed' (and is defined in col.goo but sadly is not
documented) but i like `do-map' better.

>   These seem like obvious adds. If I understood how packers work
>   there are probably analogs there, too. 
> 
> o It's also clear that the goo collection protcol is *very* heavily
>   aimed at sequences and mappings. I started out writing <treap> as a
>   set type, and then changed it into a mapping to make it actually
>   exercise the collection libraries. Right now, I don't think sets
>   fit at all comfortably into the goo collection worldview. This is
>   annoying because sets are basically the only other common kind of
>   collection, and it sure would be nice if goo could handle them
>   easily.

i'll figure out something for this.  <set>'s are now done the easy way
of subclassing <tab>'s.

> o I really like how goo generates a display for a map:
> 
>   goo/user 0<= (col <treap> 1 'a 2 'b 3 'c)
>   goo/user 0=> #<<treap> 1: a 3: c 2: b>
> 
>   It would be way cool if the reader could use that as literal syntax
>   for any kind of map. So #<<foo> 1: "a" 3: "c" 2:"b"> would morph
>   into (col <foo> 1 "a" 3 "c" 2 "b"), or something like that.

i'm working on this.  not ready for primetime.

> o I'd like an option to display backtraces automatically, and for
>   there to be line number information in errors. 

i'm on the case.

thanks for the library and the feedback!

jonathan