Fun transformation problem

[Martin Maney]

John Lenton <john at grulic.org.ar> wrote:
> FYI, that goofy dictionary thing you're building is called a 'trie'.

And in some applications it may be handy to be able to construct the
trie piece by piece, or to add entries to it.  (BTW, am I wrong in
thinking that tries in general aren't restricted to having all leaf
nodes at the same level as the examples in this all do?  Not that I'm
complaining, since I'm not going to handle that general case either!)
So I'll start with a function to add a single leaf to a trie:

def add2trie(car, cdr, trie):
    if len(cdr) == 1:
        trie[car] = cdr[0]
    else:
	if not trie.has_key(car):
            trie[car] = {}
        add2trie(cdr[0], cdr[1:], trie[car])

...and then the requested function is trivial:

def f(lstlst):
    trie = {}
    for lst in lstlst:
        add2trie(lst[0], lst[1:], trie)
    return trie

car and cdr are intrusions from you-can-guess-where that suggested
themselves in the first hack which had 'way too many occurences of lst[0]
in it.

                              <digression>

BTW, the first sketch (which I decided I didn't like for its
unnecessary rebinding of existing subtries) could have made good use of
conditional assignment (sorry, it just keeps coming up as I skim
through the backlog today).  It would have gone something like...

def add2trie(lst, trie):
    trie[lst[0]] = (if len(lst) == 2: lst[1]
                    else: add2trie(lst[1:], trie.get(lst[0], {}))
    return trie

Obviously this is untested code, and to be honest I don't much like
this form when it has to spread across lines like that.  OTOH, it's an
amusing example, since it uses within the general conditional
expression one of Python's existing special-case hacks that wouldn't be
necessary (though it might still be handy) if Python had conditional
expressions.  :-)

                             </digression>

-- 
Vs lbh pna ernq guvf, lbh'er va ivbyngvba bs
gur Qvtvgny Zvyyraavhz Pbclevtug Npg.  -- anon.