>Despite the fact that list 'n' hashes are very common, there are times I wish I was using a thoughtful tree representation. Such a model can provide richer navigation operations.

Specter[1] provides something like this for Clojure, allowing rich navigation and transformation abilities to deeply nested structures.

[1]: http://nathanmarz.com/blog/functional-navigational-programmi...

I've thought about this topic a lot recently. Many times I find myself working with API endpoints which return deeply nested JSON or XML "documents" which I have no real desire to learn their schema. (AWS and ElastiSearch)

I ended up creating a Python Library to perform key lookups on these deeply nested documents. For Example:

    >>> from nested_lookup import nested_lookup

    >>> document = [ { 'taco' : 42 } , { 'salsa' : [ { 'burrito' : { 'taco' : 69 } } ] } ]

    >>> print(nested_lookup('taco', document))
    [42, 69]

Check it out here:

* https://pypi.python.org/pypi/nested-lookup

* https://github.com/russellballestrini/nested-lookup

You might be interested in "jq", a python program that provides an expression language for extracting and transforming json data:

   https://stedolan.github.io/jq/

I've seen jq used in various places, called from bash, ends up looking pretty unwieldy.

Also briefly looking at the docs, I don't see anywhere where this nested-lookup functionality exists.

I use jq for exploring and light massaging of json data, but for complicated tasks I just write python code.

I misunderstood what your library did. jq doesn't cover that - as far as I know, there are no recursive constructs in jq.

have you heard of xpath? :)

Does that work for json or just XML?

does xpath require knowing the path? nested-lookup doesn't.

You do know you can just stick a double slash at the beginning of the path to say that you don't care where in the document it is, right?

No, I didn't know that. Thanks.

I've always wanted to write something like regular expressions for lists of objects. So, for example the example of writing a parser, one could use a regex to match chars to tokens, then write another that gathers tokens into blocks and etc. Essentially, bottom-up parsing without resorting to parser generators that take over everything. A similar tool would be interesting for querying trees directly.

OMeta is an interesting place to start, there's implementations for a ton of languages. Here's a good description of the motivation for OMeta and the .Net implementation: http://www.moserware.com/2008/06/ometa-who-what-when-where-w...

That is definitely very interesting! Writing a parser/compiler for 'x' language tends to be a component of many interesting projects, and that's definitely a good start -- thanks :)

Going into it I assumed this article was about data structures like the PHP "array", which are basically ordered hashtables that allow the programmer to treat them like either lists or hashes depending on context and still get reasonable performance. (I haven't seen this pattern used much elsewhere, has anyone?)

Lua tables are similar- they're nominally hash tables but are often used as arrays (including a length operator), and a few versions ago they added an optimization where small integer keys are stored in an actual linear array.

The optimization is actually for contiguous integer keys, starting from 1.

Aren't any hashes that keep track of order like that? (I.e. how's that different than objects in javascript, hashes in ruby, OrderedDicts in python and LinkedHashmaps in java?)

In Javascript, object properties are not ordered: http://stackoverflow.com/a/5525820/96855. The Map object would be closer: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

I'm not sure I understand why "S-expression" doesn't fit as a name for this data structure.

I wonder if the .Net/Java approach of "Iterables And Objects" with generic sequence operators either is ListAndHash or is the equivalent in more strongly typed languages. You essentially replace String->Object Hashes with Objects and Lambda lookup functions.

Finding out about "alists" and their lispy incarnation made me so happy. It was just so neat that something in some regards more capable than a typical hash table (key shadowing, references needn't be to the entire structure, ...) could spring to life, expressed in terms of barely anything atop the humble cons cell.

tldr you can have list or hashes to represent your data model, trivial observation

Yeah, but now that trivial observation has a name that he coined.

And incidentally, what a terrible name. A "hash" (really hash table) is a specific implementation of a map/dictionary. You shouldn't use "hash" to refer to a map based on search trees.

It is interesting that hash is sometimes (incorrectly) used as a synonym or generic name for map/dictionaty/associative array, but Red-Black-Tree, AVL tree, etc. is not.