Hello. In simplistic terms, a feature structure is an unordered list of attribute-value pairs.

[number:sg, person:3 | _ ],

which can be embedded:

 [cat:np, agr:[number:sg, person:3 | _ ] | _ ],

can subindex stuff and share the value

[number:[1], person:3 | _ ],

where [1] is another feature structure (that is, it allows reentrancy).

My question is: what data structure would people think this should be implemented with for later access to values, to perform unification between 2 fts, to "type" them, etc.

There is a full book on this, but it's in lisp, which simplifies list handling. So, my choices are: a hash of lists, a list of lists, or a trie. What do people think about this?