3 ms·

Given that the book opens by defining a recursive datatype, it would be an exercise in frustration to port this to Rust...

airstrike 2y ago
How so? Can't you just put your Tree in a Box? enum Tree { Leaf, Node(Box<Tree>, Box<Tree>), } fn number_of_leaves(tree: &Tree) -> u32 { match tree { Tree::Leaf => 1, Tree::Node(left, right) => number_of_leaves(left) + number_of_leaves(right), } } #[cfg(test)] mod tests { use super::*; #[test] fn counts_the_number_of_leaves_in_a_tree() { let tree_with_3_leaves = Tree::Node( Box::new(Tree::Leaf), Box::new(Tree::Node( Box::new(Tree::Leaf), Box::new(Tree::Leaf), )), ); let leaves = number_of_leaves(&tree_with_3_leaves); assert_eq!(leaves, 3); } }
- itishappy 2y ago
  Geez, that's way easier than I remembered. When I originally encountered this while learning Rust I figured recursion was my problem and switched to learning Haskell. (No regrets.) I guess I need to take my findings back to Rust!
- marcosdumay 2y ago
  Yes, and the frustration is on dealing with all the boxes and unboxing, at the exact correct place, and that won't unify with each other. There's a sibling comment about porting it to C#. The Rust version will be less frustrating than the C#, but it is the same kind of bad. On Rust specifically, this happens because Rust is a low level language.
  - neonsunset 2y ago
    The sibling comment looks way closer to port of Go which is rather unidiomatic C#. I understand where it is coming from, but there is a much terser and type-safe way to express it: #pragma warning disable CS8509 // The switch expression does not handle all possible values. // Justification: The switch expression is exhaustive, and Roslyn emits optimal default guard. // In AOT, ILC should be able to statically prove by whole program view that only two subclasses of Tree exist and optimize it away. // In practice, it seems null check and recursive nature of the call prevent it for now. It is still compact and fast codegen however. var treeWith3Leaves = new Tree.Node( new Tree.Leaf(), new Tree.Node( new Tree.Leaf(), new Tree.Leaf())); var leaves = NumberOfLeaves(treeWith3Leaves); if (leaves != 3) { throw new Exception("Huh, something went wrong."); } static int NumberOfLeaves(Tree tree) { return tree switch { Tree.Leaf => 1, Tree.Node n => NumberOfLeaves(n.Left) + NumberOfLeaves(n.Right) }; } abstract record Tree { public record Leaf: Tree; public record Node(Tree Left, Tree Right): Tree; } Once we have type unions[0], the syntax could be easily promoted (assuming current proposal state) to e.g. union Tree { Leaf; Node(Tree Left, Tree Right); } Or a bit lower-level variant: record Node(Tree Left, Tree Right); union struct Tree { Leaf; Node; } This will allow to remove exhaustiveness suppression and not pay for (house of) leaves. [0]: https://github.com/dotnet/csharplang/blob/18a527bcc1f0bdaf542d8b9a189c50068615b439/proposals/TypeUnions.md https://github.com/dotnet/csharplang/blob/18a527bcc1f0bdaf54...

airstrike 2y ago

How so? Can't you just put your Tree in a Box? enum Tree { Leaf, Node(Box<Tree>, Box<Tree>), } fn number_of_leaves(tree: &Tree) -> u32 { match tree { Tree::Leaf => 1, Tree::Node(left, right) => number_of_leaves(left) + number_of_leaves(right), } } #[cfg(test)] mod tests { use super::*; #[test] fn counts_the_number_of_leaves_in_a_tree() { let tree_with_3_leaves = Tree::Node( Box::new(Tree::Leaf), Box::new(Tree::Node( Box::new(Tree::Leaf), Box::new(Tree::Leaf), )), ); let leaves = number_of_leaves(&tree_with_3_leaves); assert_eq!(leaves, 3); } }

itishappy 2y ago
Geez, that's way easier than I remembered. When I originally encountered this while learning Rust I figured recursion was my problem and switched to learning Haskell. (No regrets.) I guess I need to take my findings back to Rust!
marcosdumay 2y ago
Yes, and the frustration is on dealing with all the boxes and unboxing, at the exact correct place, and that won't unify with each other. There's a sibling comment about porting it to C#. The Rust version will be less frustrating than the C#, but it is the same kind of bad. On Rust specifically, this happens because Rust is a low level language.
- neonsunset 2y ago
  The sibling comment looks way closer to port of Go which is rather unidiomatic C#. I understand where it is coming from, but there is a much terser and type-safe way to express it: #pragma warning disable CS8509 // The switch expression does not handle all possible values. // Justification: The switch expression is exhaustive, and Roslyn emits optimal default guard. // In AOT, ILC should be able to statically prove by whole program view that only two subclasses of Tree exist and optimize it away. // In practice, it seems null check and recursive nature of the call prevent it for now. It is still compact and fast codegen however. var treeWith3Leaves = new Tree.Node( new Tree.Leaf(), new Tree.Node( new Tree.Leaf(), new Tree.Leaf())); var leaves = NumberOfLeaves(treeWith3Leaves); if (leaves != 3) { throw new Exception("Huh, something went wrong."); } static int NumberOfLeaves(Tree tree) { return tree switch { Tree.Leaf => 1, Tree.Node n => NumberOfLeaves(n.Left) + NumberOfLeaves(n.Right) }; } abstract record Tree { public record Leaf: Tree; public record Node(Tree Left, Tree Right): Tree; } Once we have type unions[0], the syntax could be easily promoted (assuming current proposal state) to e.g. union Tree { Leaf; Node(Tree Left, Tree Right); } Or a bit lower-level variant: record Node(Tree Left, Tree Right); union struct Tree { Leaf; Node; } This will allow to remove exhaustiveness suppression and not pay for (house of) leaves. [0]: https://github.com/dotnet/csharplang/blob/18a527bcc1f0bdaf542d8b9a189c50068615b439/proposals/TypeUnions.md https://github.com/dotnet/csharplang/blob/18a527bcc1f0bdaf54...