Wed Oct 17 15:34:26 CEST 2007
operations on dictionaries
I'm trying to factor dictionary operations a bit. I already ran into
'collect' which takes a list of tagged pairs, and collects all
occurences for each unique pair. Doing this stuff purely functional
becomes difficult if performance is an issue: naive algorithms are
quadratic. Hash tables could accellerate. It seems overall that
mutation is the thing to choose here..
Trying to write these hierarchical combination things i'm getting
convinced that it's a bit of a mess.. (name . value) pairs are well
defined, but hierarchical structures require polymorphy. To make the
analogy with ordinary functions, basicly you're dealing with a
function that maps a value to a value OR another function..
Maybe the whole abstraction is broken?
I need to think about this.. something profound seems to be hidden
here. I'm going to hack around it for now.
I think I get it.. and it's trivial again.
A hierarchical hash table (HHT) is an implementation of a finite
function which maps tag SEQUENCES to values. All operations on HHTs
have the semantics of operations on finite functions.
From this follows that paths need to be created if a value is
stored. It doesn't make sense to have to create the directory before
storing a value. Otoh, storing a value in a tag sequence, where one of
the top nodes is not a hhash is an error.