CakeML / CakeML/cakeml

Add support for or-patterns

Open
#664 0 comments 0 reactions 0 assignees View on GitHub
low priority
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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.