3 ms·
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) ->
by 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 agoGeez, 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 agoYes, 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 agoThe 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...