Matching trees: 'n level' pattern requires n level nested matches?

1

  1. Let us call a node as 'level 1', its children as 'level 2', its grand children as 'level 3', ...

  2. Let us say a pattern is "level n" if it requires looking at level-n children. So a "level 1" pattern looks only at self, a "level 2" node looks at self & children, a "level 3" node looks at self + children + grand children.

  3. Now the question -- suppose we have a "level n" pattern -- does this imply we need n levels of nested 'matches'? (This seems to not be the case for languages like Haskell / OCaml).

  4. Because structs are fixed size, for tree shaped structures, we have to end up using Rc, Box, or Vec to point to the children.

  5. However, Rust match does not let us "match through" Rc / Vec (we need to call .as_ref() or .as_slice()) outside of a match.

  6. Thus, does a "level n" pattern therefore require n nested levels of match ?

2

For example, for a pattern-matching Red Black Tree, Lecture 11: Balanced Binary Trees: Red-Black Trees , we can see OCaml do:

let balance = function
    Black, z, Node (Red, y, Node (Red, x, a, b), c), d
  | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
  | Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
  | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
      Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
  | a, b, c, d ->
      Node (a, b, c, d)

It seems impossible to do this type of pattern matching in Rust, where we'd have to 'break up the pattern' at each child level, making the code less elegant and harder to read.

3

If you use nightly, you can make use of box_patterns, which makes things a bit nicer

1 Like
4

box_patterns are very cool. Any chance this generalizes to Rc + Vec ?

5

Yes, it's a really nice feature, but unfortunately it's actually been put under a feature gate on purpose, even though it used to be fine. It appears that the team wants to remove it.

https://github.com/rust-lang/rust/issues/29641

6

Although I think removing box_patterns would be stupid, I have to admit the actual Rust developers know Rust better than I do. Do you know their rationale for wanting to remove box_patterns?

7

Looks like Tracking issue for `box_patterns` feature · Issue #29641 · rust-lang/rust · GitHub provides a more general solution.

3 Likes
8

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.