OR-patterns?

[gefjon]

I'm writing a red-black tree as the implementation of a data structure I need for work, and it turns out that balance :: Tree -> Tree (the function that restores the red-black invariant to a tree after an insertion has ruined it) is a classic example of a case where OR-patterns are a huge ergonomic improvement.

For reference, here's an implementation of balance in Coalton without OR-patterns:

(declare balance (Color -> (Tree :elt) -> :elt -> (Tree :elt) -> (Tree :elt)))
(define (balance clr left elt right)
  (match (Tree clr left elt right)
    ((Tree (Black)
           (Tree (Red)
                 (Tree (Red) a x b)
                 y
                 c)
           z
           d)
     (Tree Red
           (Tree Black a x b)
           y
           (Tree Black c z d)))
    ((Tree (Black)
           (Tree (Red)
                 a
                 x
                 (Tree (Red) b y c))
           z
           d)
     (Tree Red
           (Tree Black a x b)
           y
           (Tree Black c z d)))
    ((Tree (Black)
           a
           x
           (Tree (Red)
                 (Tree (Red)
                       b
                       y
                       c)
                 z
                 d))
     (Tree Red
           (Tree Black a x b)
           y
           (Tree Black c z d)))
    ((Tree (Black)
           a
           x
           (Tree (Red)
                 b
                 y
                 (Tree (Red)
                       c
                       z
                       d)))
     (Tree Red
           (Tree Black a x b)
           y
           (Tree Black c z d)))
    (tre tre)))

I'll point out, because I don't think it's obvious at a glance, that all four interesting match arms bind the same variables from different locations on a tree, and then evaluate the same form to construct a balanced tree holding those variables.

Here's a version with a hypothetical or pattern, which I think makes what's going on much clearer:

(declare balance (Color -> (Tree :elt) -> :elt -> (Tree :elt) -> (Tree :elt)))
(define (balance clr left elt right)
  (match (Tree clr left elt right)
    ((or (Tree (Black)
           (Tree (Red)
                 (Tree (Red) a x b)
                 y
                 c)
           z
           d)
         (Tree (Black)
           (Tree (Red)
                 a
                 x
                 (Tree (Red) b y c))
           z
           d)
         (Tree (Black)
           a
           x
           (Tree (Red)
                 (Tree (Red)
                       b
                       y
                       c)
                 z
                 d))
         (Tree (Black)
           a
           x
           (Tree (Red)
                 b
                 y
                 (Tree (Red)
                       c
                       z
                       d))))
     (Tree Red
           (Tree Black a x b)
           y
           (Tree Black c z d)))
    (tre tre)))

I believe this to be a huge improvement in clarity; in the original version, it takes a bit of reading to notice that all four interesting branches are doing the same thing for slightly different tree topologies, but in the second it's immediately obvious.

And best of all, Trivia already supports OR-patterns, so the only work we need to do to support this is in typechecking.

[stylewarning]

What would be the behavior of branches not having the same variables?

[eliaslfox]

I think we would need to disallow that.

[eliaslfox]

Here is the rust rfc for comparison. They require binding the same variables in all branches. They also allow nesting or patterns which seems kinda cool.

[gefjon]

Yes, like Elias says, I think having branches in an or pattern which bind different sets of variables, or bind variables to different types, should be a typeck error.