[erlang-questions] maps iterator

[Jesper Louis Andersen]

On Wed, Sep 30, 2015 at 3:26 AM, zxq9 <zxq9@REDACTED> wrote:

> I am actually just curious how "iterator context" is maintained without
> the code becoming either highly mysterious (as in overuse of the process
> dictionary) or a different semantic label for an list operation over maps
> that merely indicates "this version of the function foo/2 is better" (so
> why have foo/2?).


You run a "zipper[0]" in the C layer. A map is a tree internally. A very
wide tree. If the iterator references the top of the tree, it won't be
garbage collected, so I have a stable snapshot of the tree. Now, if I keep
track of the "path not chosen" in the tree, inside the iterator structure,
I obtain a "cursor" on where I am in the tree and can thus traverse the
tree as in next/1, prev/1 and friends. The only data I have to store is
"where I am" as the tree data themselves are inside the snapshot.

The goal here is to use this to implement a variant of map/2 which doesn't
blit the whole map in memory before traversal. While fast, it has quite bad
memory characteristics.

[0] https://en.wikibooks.org/wiki/Haskell/Zippers


-- 
J.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20150930/dff7bfda/attachment.htm>