Disclaimer

The content of this blog is my personal opinion only. Although I am an employee - currently of Nvidia, in the past of other companies such as Iagination Technologies, MIPS, Intellectual Ventures, Intel, AMD, Motorola, and Gould - I reveal this only so that the reader may account for any possible bias I may have towards my employer's products. The statements I make here in no way represent my employer's position, nor am I authorized to speak on behalf of my employer. In fact, this posting may not even represent my personal opinion, since occasionally I play devil's advocate.

See http://docs.google.com/View?id=dcxddbtr_23cg5thdfj for photo credits.

Thursday, August 02, 2012

Pattern: Ordered Lists, with Associative Lookup and Update

One of my friends (TC) complained that XML had too much order.  He said that XML structs should be unordered, like Perl hashes, associative arrays.  Indeed, JSON has unordered key=alue pairs, and ordered lists: the former is not the latter.

I'm not so sure.  I keep running into situations where I want to have an ordered data structure, but where I also want an associative lookup and/or update.

For example, my shell PATH.  It is definitely order dependent.  But I often want to do operations such as

  • is DIR already in PATH
  • add DIR to PATH if it is not already present
    • prepend or append
  • add DIR to PATH next to DIR_already_in_path
    • just before, or just after
  • replace DIR0 in PATH (assuming it is already there) with DIR1
For example, hook lists - like hook lists for emacs.

For example, like Bash PROMPT_COMMAND. This really isn't a hook list, but imagine that it is, using ; as the separator (gets more complicated with IFs, etc.).  Here I have been wanting a more general associative lookup, not just exact matching.
  • E.g. replace any element that looks like a command that invokes my logical-path program.*logical-path.* with a different invocation of that program
Just like associative arrays, hashes, have greaty impoved programmer productivity by being built in data structures in Perl and Python (and to a weaker extent in C++ STL std::map), it may be worth thinking about standardizing ordered associative arrays. Using Perl associative array syntax (not my favorite, but it's easy at hand):
$OAA{key}  # error if more than 1 match?
$OAA{key:1} $OAA{key:2} ... # first match, second match, ...
$OAA{key:#} # number of matches
$OAA{key} = value # replace. error if no match
$OAA{key} = {} # delete - or some other way of indicating droppage
$OAA{key} <<= value # insert just before
$OAA{key} >>= value # insert just after
$OAA{key:*} = ... # replace all occurrences
We might distinguish key from value, as in key=value.  Or we might allow the key and the value to be the same, i.e. the entire value might be matched against.

We might require key to be exactly matched - or we might allow regexps, or arbitrary expressions.
$OAA{i WHERE $OAA{i} < 2} = ... # replace all occurrences
We might allow the value to have structure, with fields.
$OAA{rec WHERE $OAA{rec}.age > 10 and $OAA{rec}.weight <70 br="br">$OAA{.age > 10 and .weight <70 blockquote="blockquote">Nothing that you can't do with map here - but the notation may be more pleasant. And compact, pleasant notation matters. (As opposed to compact unpleasant notation.)

Verges on relations.

---

Extend to multi dimensional?



No comments: