Dictionaries with array-like interface

[dmm]

This low-key talk might have been the single most useful talk of the whole JuliaCon 2021:

Dictionaries.jl - for improved productivity and performance

pretalx.com/juliacon2021/talk/WRNAEN/

and live.juliacon.org/talk/WRNAEN (that is, www.youtube.com/watch?v=Y-hAZcqAw28)

github.com/andyferris/Dictionaries.jl

I am going to recall my recent brushes with advanced dictionaries (and with their reshaping into arrays) in the comments.

Comments

[dmm]

On one hand, there is my research draft of what one could do to accommodate nested dictionaries (structure with tree-like interfaces) inside machine learning frameworks optimized for hangling "tensors" (flat multidimensional arrays).

https://github.com/anhinga/2021-notes/tree/main/research-drafts

"Dataflow matrix machines, tree-shaped flexible tensors, neural architecture search, and PyTorch" (Jan 2021)

[dmm]

One notable thing in that research draft is the mention of "minimal perfect hashes" (and a particular implementation of those) on page 5 (section 5.3).

[dmm]

Of course, it is an interesting question whether it's worthwhile to try to upgrade rigid frameworks to more flexible situations handling tree-like data structures and such.

If the promise of "differential programming" would be realized already, I would say "no".

But in reality, at least in Julia, the insightful statements that AD (automatic differentiation) is foundational for a modern science-oriented and machine-learning oriented programming language are great, but in reality the state-of-the-art AD Julia ecosystem still contains too many defects and is difficult to use. Hopefully, this will be improve soon (and perhaps I'll participate in this improvement).

I have not tried JAX yet, so I don't know if things are better on the Python side of the fence.

And if "differential programming" state-of-the-art in the latest generation of machine learning frameworks is so-so, retrofitting the flexibility into something old and rigid like PyTorch might still be an interesting idea.

[dmm]

Then there is https://en.wikipedia.org/wiki/Hash_tree_(persistent_data_structure)

which is presumably behind all modern implementation of persistent data structures in Clojure and other languages:

https://lampwww.epfl.ch/papers/idealhashtrees.pdf (also posted here https://hashingit.com/elements/research-resources/2001-ideal-hash-trees.pdf )

These ideal hash trees are more like Tries ("Hash Array Mapped Trie").

Array Mapped Tries(AMT), first described in "Fast and Space Efficient Trie Searches", Bagwell [2000], form the underlying data structure.

[dmm]

In this sense, in Julia we have https://github.com/JuliaCollections/FunctionalCollections.jl

with "PersistentHashMap" and such, with the foundational file being "src/BitmappedVectorTrie.jl".