[HN Gopher] Fast Functional Lists, Hash-Lists, Deques and Variab...
       ___________________________________________________________________
        
       Fast Functional Lists, Hash-Lists, Deques and Variable Length
       Arrays [pdf] (2002)
        
       Author : tosh
       Score  : 39 points
       Date   : 2022-11-05 10:30 UTC (2 days ago)
        
 (HTM) web link (trout.me.uk)
 (TXT) w3m dump (trout.me.uk)
        
       | [deleted]
        
       | eddsh1994 wrote:
       | This needs [2002]
        
       | lichtenberger wrote:
       | Phil Bagwells work is amazing. Especially the Hash Array Mapped
       | Trie (HAMT) for me was an eye opener, as we had implemented a
       | simple arrays based trie more or less for 64bit integers before
       | and I always wondered how to compress the null pointers to
       | children, which are non-existent. Nowadays I'm using ideas from
       | the HAMT and the Adaptive Radix Trie (ART) to compress the trie
       | nodes. Cool thing of course is also that each previous version is
       | preserved through structure sharing and copy-on-write plus path
       | copying (functional data structure, again).
        
       | tromp wrote:
       | The very rough idea is that vlists are lists of arrays whose size
       | decreases exponentially towards the tail of the list. So "hello,
       | world" could be stored as                   "hello" -> ", wo" ->
       | "rl" -> "d"
       | 
       | with space for 3 more characters to be consed in front of
       | "hello".
        
       ___________________________________________________________________
       (page generated 2022-11-07 23:01 UTC)