[Agda] red black trees with delete

Andreas Abel andreas.abel at ifi.lmu.de
Wed Jan 11 15:43:08 CET 2012


Hello Jonathan,

you might be interested to compare your solution to Julien Oster's.

   https://bitbucket.org/anyfoo/agda-std-trees/src

Cheers,
Andreas

On 1/11/12 2:04 PM, Nils Anders Danielsson wrote:
> On 2012-01-11 03:36, jleivent at comcast.net wrote:
>> Since I'm a novice at dependent-typed programming, I'm not sure if
>> this is a trivial result or not. However, one interesting thing is
>> that I didn't previously know or refer to any existing red black tree
>> implementation of delete - I just allowed the combination of the Agda
>> type checker and the exacting dependent type signatures to do their
>> thing (with some simple reasoning about what the delete function must
>> contain - such as a delete minimum function) - making me feel more
>> like a facilitator than a programmer.
>
> I had a similar experience when implementing the AVL trees in the
> standard library. I had never implemented tree rotations, but once I had
> the types in place (at that time primarily balancing information) the
> rotations almost wrote themselves.
>

-- 
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

andreas.abel at ifi.lmu.de
http://www2.tcs.ifi.lmu.de/~abel/


More information about the Agda mailing list