Add support for or-patterns
- Dominant language
- Standard ML
- Stars
- 1.2k
- Forks
- 104
- Avg merge
- 2d 21h
- Merged PRs (30d)
- 16
Description
A famous example of a very useful or-pattern is the following balance function from Okasaki's presentation of red-black trees:
```
let balance = function
| (Black, Node (Red, Node (Red, a, x, b), y, c), z, d)
| (Black, Node (Red, a, x, Node (Red, b, y, c)), z, d)
| (Black, a, x, Node (Red, Node (Red, b, y, c), z, d))
| (Black, a, x, Node (Red, b, y, Node (Red, c, z, d))) ->
Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d))
| (c,a,x,y) -> Node (c,a,x,y)
```
The encoding of such top-level or-pattern using a function is less pretty:
```
let balance t =
let k a x b y c z d = Node (Red, Node (Black, a, x, b), y, Node (Black, c, z, d)) in
match t with
| (Black, Node (Red, Node (Red, a, x, b), y, c), z, d) -> k a x b y c z d
| (Black, Node (Red, a, x, Node (Red, b, y, c)), z, d) -> k a x b y c z d
| (Black, a, x, Node (Red, Node (Red, b, y, c), z, d)) -> k a x b y c z d
| (Black, a, x, Node (Red, b, y, Node (Red, c, z, d))) -> k a x b y c z d
| (c,a,x,y) -> Node (c,a,x,y)
```
In-depth or-patterns are much less frequent in practice. Main use case that I know of is to deal with symmetries. E.g. the pattern `(None, Some x) | (Some x, None)` occuring in depth.
I beleive it is fine to either not support those, or to encode them in a naive manner by lifting the disjunction to the top level (documenting clearly that in the worst case this is exponential in the number of or-clauses appearing in parallel within the same pattern).
Contributor guide
No contributing guide indexed for this repository
Research direction
No files, tests, or entry points are named in the issue. Start by locating the pattern-matching implementation and existing tests, then determine how the shown top-level and nested or-pattern examples should be represented. Done means the examples are supported with documented behavior and passing tests.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 20/100