Is there a more conventional / standard / easy-to-read way of building an index of tuples from an iterable than this:# -----------------------------------------------------------------------------def build_index(itable_tup):        Return an index for an iterable container of tuples, all the same length.    The last element in each tuple is treated as the payload value    that is to be indexed, and the preceeding elements as a hierarchy    of indices by which it is to be indexed.    The index itself is a nested default-dictionary with len(tup)    levels of nesting, containing a list at the innermost level    to hold the payload.    >>> idx = build_index((('a','b', 1), ('a','c', 2)))    >>> import json    >>> print(json.dumps(idx, sort_keys=True))    {a: {b: [1], c: [2]}}    This function is a bit of an exercise in making use of the    functional programming capabilities that come with Python,    so the  implementation is a little more terse and opaque    than it might otherwise be...    For each tuple in iter_tup, we construct a slot in the index    using the lazy initialisation capability that is provided by    the collections.defaultdict class. All but the last element    in the tuple are used for indexing. The last element is the    payload which gets added to the inner list after the structure    has been initialised. The basic capability is provided by    the nested defaultdict data structure returned from the idx_ctor    function, which in turn is built with the aid of the higher    order lambda function (_partial(_dedict, ctor)).    All this is plugged together using calls to functools.reduce,    which is used to construct the custom index data structure; to    add each tuple to the index, as well as to iterate over the    input.        _dedict   = collections.defaultdict    _chain    = itertools.chain    _repeat   = itertools.repeat    _reduce   = functools.reduce    _partial  = functools.partial    _getitem  = operator.getitem    # Peek ahead to determine the tuple length (& reconstitute the iterator).    iter_tup  = iter(itable_tup)    try:        first_tup = iter_tup.__next__()    except StopIteration:        return {}    idx_depth = len(first_tup) - 1    iter_all  = _chain([first_tup], iter_tup)    # Create a constructor for a custom index data structure.    idx_ctor = _reduce(lambda ctor, _: _partial(_dedict, ctor),                       _repeat(None, idx_depth), list)    # This function adds a sigle tuple to the custom index data structure.    def _add_tup_to_idx(idx, tup):                Add a sigle tuple to the custom index data structure.                _reduce(_getitem, tup[:-1], idx).append(tup[-1])        return idx    # This iterates over all tuples adding each to the index in turn.    return _reduce(_add_tup_to_idx, iter_all, idx_ctor())
Building an index of items from an iterable-of-tuples
python;algorithm;python 3.x
Don't use make variables scoped to a function 'private'.They're 'protected' so please, just remove the _ from them.If we look at your next block.You use iter_tup.__next__().Don't.Use next!If you see __{name}__ then you should always check if there is a better way.And so I'd use:first = next(iterator, None)if first is None:    return {}The next block to get the length and to rebuild the iterator is fine.The reduce is fine, I dislike how static it is.And so if I were to write this function I'd change it.But it's fine.I'd change _add_tup_to_idx to just a plain for loop.Sure it means you mutate something, oh well.It's much easier to read and understand.I'd change it to:dictionary = idx_ctor()for tup in iter_all:    reduce(_getitem, tup[:-1], dictionary).append(tup[-1])return dictionaryFinally I'll go over a few more 'high-level' things. It's much easier to read if you use good variable names.Take for example:def build_index(iterator):    iterator = iter(iterator)    first = next(iterator)    if first is None:        return {}    depth = len(first) - 1    iterator = chain([first], iterator)    ddict = reduce(lambda d, _: partial(defaultdict, d),                   repeat(None, depth),                   list)    dictionary = ddict()    for item in iterator:        reduce(getitem, item[:-1], dictionary).append(item[-1])    return dictionaryNow you seem to put emphasis on it being a hash-tree.But what do you get if you do:build_index((('a',), ('b',), ('c',)))Is it a dictionary, or is it a list?Now what do you get if you enter these:build_index((('a', 'b'), ('b', 'c'), ('c', 'd')))build_index(())Yes the they return different types.The above two are dictionary's, and the first is a list.That is a massive edge case.I think the design should be based around an infinite default dict.And for it to always return a dict.And so you could use the following recursive function:def ddict():    return defaultdict(ddict)Now we just have to change your for loop.If we slice the string into two at the second to last position,and remove the item from the list if the second is empty:dictionary = ddict()for head, tail in ((i[:-2], i[-2:]) for i in iterable):    if not tail:        continueNow before you say, that's not functional!Yeah it's half functional, well the comprehension is.It's easier to read this way, as if Python were a functional based language it'd be more like:iterable    .map(i => (i[:-2], i[-2:]))    .filter(i => i[1])Now we could do that, but it'd be icky, take:(i for i in ((i[:-2], i[-2:]) for i in iterable) if i[0])filter(lambda i: i[0], map(lambda i: (i[:-2], i[-2:]), iterable))And so they all are the same, so just go for the most readable.For the last bit, we will do what you were doing before.But with two changes.To allow for tail to have a length of one, we need to use extend rather than append.and to get a list you'll have to use setdefault with a list.This gives a quite functional function:def build_index(iterable):    def ddict():        return defaultdict(ddict)    dictionary = ddict()    for head, tail in ((i[:-2], i[-2:]) for i in iterable):        if not tail:            continue        (reduce(getitem, head, dictionary)            .setdefault(tail[0], [])            .extend(tail[1:]))    return dictionaryYou can also change getitem to a function that uses setdefault to remove the need for defaultdict and getitem.