Module fungi_lang::examples

Examples of data structures and algorithms in Fungi.

Basics

These (very small) examples demonstrate basic concepts from Fungi’s type and effect system:

• basic_read_effects — read effects track the reference cells and thunks that a Fungi program observes and forces.
• basic_write_effects — write effects track the reference cells and thunks that a Fungi program allocates.
• basic_write_scope — write scopes distinctly qualify written names for different dynamic calling contexts.
• basic_subtyping — subtyping permits structures with fewer names to be used in contexts that expect more names.
• basic_existentials — existential types permit packing names and named structures into types that approximate them.

FP Basics in Fungi

Basic patterns from functional programming (FP), in the “pure” fragment of Fungi. The pure effect (written 0, for short) means that a computation lacks read and write effects.

• op_nat — Simple primitives for optional natural numbers
• pure_list_nat — Simple primitives for lists of natural numbers

Lists

Linked lists whose cons cells contain names, and whose tail pointers are (named) reference cells.

• list_nat — Primitives for lists of natural numbers
• list_nat_dedup — Deduplicate input list elements; uses a hash trie

Tries

Hash tries that represent functional sets, with named elements.

• trie_nat — Primitives for tries of natural numbers

Sequences

Sequences of natural numbers, represented as probabilistically-balanced binary trees (level trees), with names and reference cells:

• seq_max — finds the maximum element in a sequence.
• seq_filter — filters a sequence of elements, producing a new (smaller) sequence.

Modules

basic_existentials

basic_hostobj

basic_read_effects

basic_subtyping

basic_write_effects

basic_write_scope

list_nat

list_nat_convert

list_nat_dedup

list_nat_edit

list_nat_reverse

name

nat

Primitive utilities:

op_nat

Optional natural numbers

pure_list_nat

Lists of natural numbers, without names, and with pure operations.

ref_edit

seq_filter

Filter a sequence of elements, producing a new (smaller) sequence

seq_max

Find the maximum element in a sequence

seq_nat

seq_nat_dfs

seq_nat_gen

trie_nat