Module fungi_lang::stdlib::list

Linked lists.

Linked lists in Fungi

In most functional languages, linked lists play a central role in organizing sequential data. In Fungi, linked lists represent "iterators", sequences in the midst of being processed or transformed. To be incrementally efficient, Fungi programs do not use linked list representations to structure recursive folds; instead, they use a balanced tree representation for sequences.

In Fungi, computations induce dependency graphs that the runtime system traverses during change propagation, and computations over linked lists produce severely degenerate (unbalanced) recursive sub-computations. As a result, we reconsider the role of linked lists in our incremental functional programs, and use them in fewer contexts than in our ordinary (non-incremental) programs.

To organize sequences for efficient random accesses, random updates or incremental folds, Fungi programs use balanced level trees. In particular, before a Fungi program iterates over a linked list, it creates a balanced level tree from its elements to better organize later incremental reuse, via change propagation.

Functions

fgi_module