4 ms·

I think functional languages handle this nicely with Foldable or Traversable typeclasses: https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-Foldable.h

• dtech 1y ago
  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]
• munchler 1y ago
  Agreed. It’s amusing to see procedural programmers slowly rediscovering what functional programmers have known for years. Paul Graham called this “The Blub Paradox”.
• agnishom 1y ago
  This becomes even better with Recursion Schemes https://hackage.haskell.org/package/recursion-schemes https://hackage.haskell.org/package/recursion-schemes
  • trealira 1y ago
    I do think recursion schemes are pretty cool, particularly the idea that a list fold could be generalized to the concept of catamorphisms, which could be mechanically derived upon defining a data structure, because the shape of the recursion that's defined is the same as the shape of the recursion of the data constructors. It makes me realize that programming languages still could be higher-level; what if a programming language automatically derived the equivalent of the "fold" and "map" functions for any recursive data type defined by the programmer? At the same time, the way it's implemented in Haskell's recursion-schemes library might be hard to wrap one's head around at first, kind of like how the list functions "foldr" and "foldl" are also often confusing to newbies, even though they're like the go-to, default way to make list functions in Haskell.
    • s-zeng 1y ago
      Haskell already supports deriving Functor and Foldable
      • trealira 1y ago
        Forgot about that lol, my bad. I was really thinking of deriving the equivalent of catamorphisms.