Nested and Composite Structures

Arrays of Maps

An array of maps is useful when you have a sequence of records, each with the same set of named fields. Consider a list of books:

nex> let books: Array[Map[String, Any]] := [
     {"title": "Dune", "author": "Frank Herbert", "year": 1965},
     {"title": "Neuromancer", "author": "William Gibson", "year": 1984},
     {"title": "Foundation", "author": "Isaac Asimov", "year": 1951}
  ]

nex> books.length
3

nex> books.get(0).get("title")
"Dune"

nex> books.get(1).get("author")
"William Gibson"

Each element of the array is a map from field name to field value. The value type is Any because different fields hold different types — strings for title and author, an integer for year.

Accessing a field in a record requires two steps: first retrieve the map from the array by index, then retrieve the value from the map by key. The chain books.get(0).get("title") reads naturally as: the title of the first book.

Iterating over all records follows the same pattern as iterating over any array:

nex> across books as book do
     print(book.get("title") + " (" + book.get("year").to_string + ")")
  end
"Dune (1965)"
"Neuromancer (1984)"
"Foundation (1951)"

The convert Expression

Nested structures often use Any at the boundary, because not every value in a map has the same type. Before using one of those values as an Integer, String, or some other specific type, you often need to check whether it really has that type.

That is what convert does:

if convert expr to name: Type then
   -- use name here
end

If the conversion succeeds, name is bound inside the then branch with the requested type. If it fails, the branch is skipped.

For example:

nex> if convert books.get(0).get("year") to year: Integer then
     print(year + 1)
  end
1966

This is especially useful when working with maps such as Map[String, Any], where a key may or may not hold the kind of value you expect.

To find records matching a condition — all books published before 1970, say:

nex> across books as book do
     if convert book.get("year") to year: Integer then
        if year < 1970 then
           print(book.get("title"))
        end
     end
  end
"Dune"
"Foundation"

Maps of Arrays

A map of arrays is useful when you want to group items under named categories. Consider a timetable that maps each day of the week to a list of classes:

nex> let timetable: Map[String, Array[String]] := {
     "Monday":    ["Maths", "Physics", "History"],
     "Tuesday":   ["English", "Chemistry"],
     "Wednesday": ["Maths", "Biology", "PE"]
  }

nex> timetable.get("Monday")
["Maths", "Physics", "History"]

nex> timetable.get("Monday").length
3

nex> timetable.get("Tuesday").get(0)
"English"

Accessing the first class on Tuesday requires two steps: retrieve the array for "Tuesday", then get its first element. The chain timetable.get("Tuesday").get(0) reads as: the first class on Tuesday.

To iterate over all days and their classes:

nex> across timetable.keys as day do
     print(day + ":")
     across timetable.get(day) as cls do
        print("  " + cls)
     end
  end
"Monday:"
  "Maths"
  "Physics"
  "History"
"Tuesday:"
  "English"
  "Chemistry"
"Wednesday:"
  "Maths"
  "Biology"
  "PE"

The outer loop iterates over days; the inner loop iterates over the classes for each day. This nested across pattern is the natural way to traverse a map of arrays.

Building Nested Structures Programmatically

Nested structures are often built up incrementally rather than written as literals. The gradebook example: given a list of (student, score) pairs, build a map from each student to their array of scores.

nex> function build_gradebook(entries: Array[Map[String, Any]]): Map[String, Array[Integer]] 
     do
       result := {}
       across entries as entry do
         if convert entry.get("name") to name: String then
           let current := result.try_get(name, [])
             if convert entry.get("score") to score: Integer then
               current.add(score)
               result.set(name, current)
             end
          end
      end
   end

nex> let entries: Array[Map[String, Any]] := [
     {"name": "Alice", "score": 85},
     {"name": "Bob",   "score": 72},
     {"name": "Alice", "score": 91},
     {"name": "Bob",   "score": 68},
     {"name": "Alice", "score": 88}
  ]

nex> let gradebook := build_gradebook(entries)
nex> gradebook.get("Alice")
[85, 91, 88]

nex> gradebook.get("Bob")
[72, 68]

The try_get(name, []) call retrieves the existing array for that student, or an empty array if the student has not appeared yet. Then add appends the new score, and set stores the updated array back. This try-get-modify-set sequence is the standard idiom for building maps of mutable values.

When Flat Structures Are Enough

Nesting adds expressive power but also adds complexity. Before reaching for a nested structure, ask whether a flat one would serve equally well.

A flat structure is sufficient when:

• Each item has only one piece of associated data. A map from student name to a single score does not need an array as the value type.
• The relationships between items are simple and uniform. If every student has exactly three scores, three separate maps — one per assignment — may be clearer than one map of arrays.
• You need to sort, filter, or search across the whole collection. Flat arrays are easier to sort and filter than nested maps.

Nesting becomes necessary when:

• Items have a variable number of associated values. A student may have one score or twenty; an array of arrays handles both without special cases.
• Items have multiple named attributes of different types. A book record with title, author, and year cannot be represented as a single flat value.
• The data has genuine hierarchical structure — categories containing items, items containing sub-items — that would be obscured by flattening.

The rule of thumb: use the simplest structure that accurately represents the data. Nesting for its own sake makes code harder to read and harder to get right.

Tree-Shaped Data

Some data is genuinely hierarchical: file systems with directories containing files and subdirectories, organisation charts with managers having direct reports, category trees with subcategories. These are tree-shaped — each node may contain other nodes of the same kind.

Nex does not have a built-in tree type. Trees are represented using maps, where each node is a map with a value field and a children field that holds an array of child nodes. Here is a simple representation of a file system fragment:

nex> let filesystem: Map[String, Any] := {
     "name": "root",
     "type": "dir",
     "children": [
        {
           "name": "documents",
           "type": "dir",
           "children": [
              {"name": "report.txt", "type": "file", "children": []},
              {"name": "notes.txt", "type": "file", "children": []}
           ]
        },
        {
           "name": "pictures",
           "type": "dir",
           "children": [
              {"name": "photo.jpg", "type": "file", "children": []}
           ]
        }
     ]
  }

Each node is a Map[String, Any]: a "name" field (string), a "type" field (string), and a "children" field (array of maps). Files have empty children arrays; directories have non-empty ones.

Traversing a Tree

Traversing a tree — visiting every node — is a naturally recursive operation. The base case is a node with no children (a leaf). The recursive case processes the node and then recursively traverses each child.

nex> function print_tree(node: Map[String, Any], indent: Integer) 
     do
       let padding: String := ""
       from let i := 0 until i >= indent do
         padding := padding + "  "
         i := i + 1
       end
       if convert node.get("name") to name: String then
         print(padding + name)
       end
       if convert node.get("children") to children: Array[Map[String, Any]] then
         across children as child do
           print_tree(child, indent + 1)
         end
       end
     end

nex> print_tree(filesystem, 0)
"root"
  "documents"
    "report.txt"
    "notes.txt"
  "pictures"
    "photo.jpg"

The function takes a node and an indentation level. It prints the node’s name with the appropriate leading spaces, then recursively prints each child at one level deeper. The recursion terminates when children is empty — across on an empty array performs zero iterations, so no further calls are made.

This is the recursive structure from Chapter 8 applied to a tree: process the current element, then recurse on the rest. The difference from list recursion is that each node may have multiple children, not just one, so the recursion branches at each level.

Searching a Tree

Finding a node by name requires the same recursive structure:

nex> function find_node(node: Map[String, Any], target: String): ?Map[String, Any] 
     do
     if node.get("name") = target then
        result := node
     else
        result := nil
        across node.get("children") as child do
           let found := find_node(child, target)
           if found /= nil then
              result := found
           end
        end
     end
   end

nex> let found := find_node(filesystem, "notes.txt")
nex> if found /= nil then
     print(found.get("name"))
  end
"notes.txt"

nex> let missing := find_node(filesystem, "missing.txt")
nex> missing
nil

The return type is ?Map[String, Any] — a detachable map, because the search may find nothing. The function returns the node if its name matches, otherwise searches the children and returns the first match found, or nil if none is found.

This pattern — returning nil to signal “not found” — is the right use of detachable types: the absence of a result is a meaningful outcome, not an error.

A Worked Example: Category Totals

Consider an expense tracker where expenses are grouped by category, and categories can contain subcategories. Each node has a "label", an "amount" (its own expenses, not including children), and a "children" array of subcategory nodes.

nex> let expenses := {
     "label": "Total",
     "amount": 0,
     "children": [
        {
           "label": "Housing",
           "amount": 1200,
           "children": [
              {"label": "Rent",       "amount": 900,  "children": []},
              {"label": "Utilities", "amount": 300, "children": []}
           ]
        },
        {
           "label": "Food",
           "amount": 150,
           "children": [
              {"label": "Groceries",  "amount": 400,  "children": []},
              {"label": "Dining out", "amount": 200, "children": []}
           ]
        }
     ]
  }

A function that computes the total amount for a node, including all descendants:

nex> function total_amount(node: Map[String, Any]): Integer 
     do
       result := node.get("amount")
       across node.get("children") as child do
         result := result + total_amount(child)
       end
   end

nex> total_amount(expenses)
3150

nex> when convert expenses.get("children") to children: Array[Map[String, Any]] then 
       total_amount(children.get(0)) 
     else 
       0 
     end
2400

The total for the root node is the sum of every amount in the tree: 0 (root) + 1200 (Housing) + 900 (Rent) + 300 (Utilities) + 150 (Food) + 400 (Groceries) + 200 (Dining out) = 3150. Work through it by hand before trusting the function — the recursive structure makes it easy to miscount.

nex> total_amount(expenses)
3150

The function is concise because the recursive structure of the data and the recursive structure of the function align perfectly. Each node’s total is its own amount plus the sum of its children’s totals — and that is exactly what the function computes.

Iterating Over Your Own Types

So far across has iterated over built-in collections — arrays, maps, and the nested structures built from them. But across is not limited to built-in types. It works with any object that knows how to produce a cursor: a small helper that visits the elements one at a time. By giving a class a cursor method you make your own composite type iterable, so client code can loop over it with the same across it uses for an array.

A cursor is an object that implements four features — the Cursor protocol:

• start — position the cursor at the first element
• item — return the element at the current position
• next — advance to the following element
• at_end — report whether the traversal is finished

When you write across some_object as x do … end, Nex calls some_object.cursor to obtain a cursor, then drives that cursor: it calls start once, and repeats item / next until at_end becomes true. The built-in collections work exactly this way — an array hands back an ArrayCursor, a map a MapCursor — which is why one loop form works uniformly across all of them.

Consider an Interval — an inclusive range of integers — that does not store its values in an array at all, but generates them on demand. First the cursor that walks the range:

nex> class Interval_Cursor
       create
         make(lo, hi: Integer) do current := lo  last := hi end
       feature
         current: Integer
         last: Integer
         start()           do end
         item(): Integer   do result := current end
         next()            do current := current + 1 end
         at_end(): Boolean do result := current > last end
     end

The cursor holds its own position in current. It starts already on the first element, so start has nothing to do; item reads the current value; next moves forward; and at_end is true once it has stepped past last. Now the Interval itself, whose only job is to hand out a fresh cursor:

nex> class Interval
       create
         make(lo, hi: Integer)
           require ordered: lo <= hi
           do low := lo  high := hi end
       feature
         low: Integer
         high: Integer
         cursor(): Interval_Cursor
           do result := create Interval_Cursor.make(low, high) end
     end

That is all it takes. An Interval is now a first-class iterable:

nex> let week := create Interval.make(1, 7)
nex> across week as day do
       print(day)
     end
1
2
3
4
5
6
7

Each cursor call returns a new, independent cursor, so the same Interval can be iterated more than once, and even nested inside another loop over itself, without the traversals interfering.

One detail carries over from Section 11.2. Because a user-defined cursor can yield elements of any type, the loop variable for a custom iterable comes through as Any. When you only print it, that is fine — print and to_string accept Any. But to use it as a number you narrow it with convert, exactly as you would a value pulled from a map of Any:

nex> let total := 0
nex> across (create Interval.make(1, 100)) as n do
       if convert n to value: Integer then
          total := total + value
       end
     end
nex> total
5050

The lesson generalises beyond ranges. Any class that models a collection — a ring buffer, a linked list, a tree with a chosen traversal order — becomes usable with across the moment it can produce a cursor. The iteration protocol is the seam: clients write one familiar loop, while each type decides privately how its elements are stored and produced.

Summary

• Arrays of maps model sequences of records; each element is a map of named fields
• Maps of arrays model grouped data; each value is a list of items under a key
• Access chains — collection.get(key_or_index).get(key_or_index) — navigate into nested structures
• Build nested structures with the try-get-modify-put idiom: retrieve the existing inner value (or a default), modify it, put it back
• Use flat structures when items have one associated value and relationships are uniform; use nesting when items have variable numbers of values, multiple named attributes, or genuine hierarchical structure
• Trees are represented as maps with a children field containing an array of child nodes
• Tree traversal and search are naturally recursive: process the current node, recurse on each child; the base case is an empty children array
• Detachable return types (?Type) are the right way to signal “not found” from a search function
• Any class becomes usable with across by giving it a cursor method that returns an object implementing the Cursor protocol — start, item, next, at_end — which is how the built-in collections work too; narrow the Any loop variable with convert when you need its concrete type

Exercises

1. Given the books array from Section 11.1, write a function books_by_author(books: Array[Map[String, Any]], author: String): Array[Map[String, Any]] that returns a new array containing only the books by the given author. Test it by finding all books by a specific author in a list that includes duplicates.

2. Write a function invert_index(books: Array[Map[String, Any]]): Map[String, Array[String]] that takes the books array and returns a map from each author to an array of their book titles. For example, if Herbert wrote two books, result.get("Frank Herbert") should return an array of both titles.

3. Using the filesystem tree from Section 11.6, write a function count_files(node: Map[String, Any]): Integer that recursively counts the total number of file nodes (nodes whose "type" is "file"). Verify that count_files(filesystem) returns 3.

4. Write a function tree_depth(node: Map[String, Any]): Integer that returns the maximum depth of the tree rooted at node. A leaf node (empty children) has depth 0. A node with children has depth equal to 1 plus the maximum depth of its children. Test it on the filesystem tree (expected depth: 2) and a single-node tree (expected depth: 0).

5.* Write a function flatten(node: Map[String, Any]): Array[String] that returns an array of the names of all nodes in the tree in depth-first order — that is, a node appears before its children, and children are listed in order. For the filesystem tree the result should be ["root", "documents", "report.txt", "notes.txt", "pictures", "photo.jpg"]. Then write a second function flatten_leaves(node: Map[String, Any]): Array[String] that returns only the leaf nodes (files). Use flatten or the same recursive pattern as a starting point.

6. Following the Interval example from Section 11.10, write a class Countdown whose constructor takes a positive integer n and that, when iterated with across, yields n, n-1, …, 1. Give it a cursor implementing start, item, next, and at_end, and a cursor method that returns a fresh one. Verify that across (create Countdown.make(5)) as k do print(k) end prints 5 down to 1, and that iterating the same object twice produces the full sequence both times.

7.* Make the Stack[T] class from the standard library example iterable from top to bottom by adding a cursor method, without exposing its underlying array. Then write a loop that uses convert to total the elements of a Stack[Integer], and explain why the loop variable arrives as Any.