Iterator

Idea: allow a container/aggregate object to provide access to its elements without exposing its internals. An iterator can allow for sequence-by-sequence traversal of lists, trees, and more.

Connection: iterators typically store a context that allows them to iterate on-demand (see “external iteration”), and this is very similar to the zipper monad in Haskell.

Note: implementing iteration is likely more complicated than you think  - see this great blog post by Bob Nystrom.

Below is an example of an external tree iterator (in-order).

class TreeNode {
  left: TreeNode | null;
  right: TreeNode | null;
  value: any;

  constructor(value: any, left: TreeNode | null, right: TreeNode | null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

class InOrderTreeIterator {
  state: TreeNode[];
  i: number = 0;

  constructor(node: TreeNode) {
    this.state = this.flatten(node);
  }

  private flatten(node: TreeNode): TreeNode[] {
    let ret: TreeNode[] = [];
    if (node.left) {
      ret = ret.concat(this.flatten(node.left));
    }
    ret.push(node.value);
    if (node.right) {
      ret = ret.concat(this.flatten(node.right));
    }
    return ret;
  }

  next() {
    if (!this.empty()) {
      return this.state[this.i++];
    }
    return null;
  }

  empty() {
    return this.i >= this.state.length;
  }
}

function main() {
  const tree = new TreeNode("d",
    new TreeNode("b",
      new TreeNode("a", null, null),
      new TreeNode("c", null, null),
    ),
    new TreeNode("e",
      null,
      new TreeNode("f", null, null)
    ),
  )
  const treeIter = new InOrderTreeIterator(tree);

  let curr: any;
  while (curr = treeIter.next()) {
    console.log(curr) // "a  b  c  d  e  f"
  }
}