4 ms·

Folding and traversing can be trivially done in all relevant programming languages if you have an iterator

• trealira 1y ago
  I feel like programming an iterator like this akin to a state machine is just not that convenient or trivial, though. Below is pseudo-Java. class InOrderTreeIterator { Stack stack; TreeNode cursor; InOrderTreeIterator(TreeNode root) { cursor = root; s = new Stack; } bool hasNext() { return cursor != null || !stack.empty(); } TreeNode next() { if (cursor != null) { while (cursor.left != null) { stack.push(cursor); cursor = cursor.left; } } else if (!stack.empty()) { cursor = stack.pop(); } else { throw new NoSuchElementException(); } TreeNode ret = cursor; cursor = cursor.right return ret; } }
  • munificent 1y ago
    It's much easier if the language has built-in support for generators. Here's an in-order tree iterator in Dart: Iterable<TreeNode> inOrder(TreeNode node) sync* { if (node.left != null) yield* inOrder(node.left!); yield node; if (node.right != null) yield* inOrder(node.right!); }
    • trealira 1y ago
      Yeah, if it has built-in support for generators, it basically makes the state machine implicit for you, which is nice and convenient; it's like going from having to manage your own stack call stack to using a programming language that just allows function calls and recursion.
• ookdatnog 1y ago
  Don't iterators necessarily "forget" the structure of the tree? I can see how you can write an iterator to, for example, compute the size of a tree, or generate the set of all variables that occur in an expression tree. But it's not obvious to me how you'd write a generic iterator that supports something like finding all free variables in an expression tree, or even just express a tree mapping function that constructs a new tree with the same structure (for example, "make all variables in the expression uppercase"). It's been a while since I worked with iterators so correct me if I'm wrong and this is in fact easy with iterators. With something like Haskell's recursion-schemes library [0] these operations are all just a few lines long, guaranteed to terminate, and don't need to be updated if your data structure changes (for example you add new expression nodes). I'm not aware of any non-functional programming language that can do that. See for example the freeVars function at the bottom of the linked recursion-schemes doc. [0] https://hackage.haskell.org/package/recursion-schemes-5.2.3 https://hackage.haskell.org/package/recursion-schemes-5.2.3
• deleted 1y ago
  [deleted]