|
# Exhaustiveness/Redundancy Check \[To Be Updated Soon\]
|
|
# Exhaustiveness/Redundancy Check
|
|
|
|
|
|
|
|
|
|
As stated in [\#595](https://gitlab.haskell.org//ghc/ghc/issues/595), GHC's overlapping/non-exhaustive pattern checking is old and
|
|
As stated in [\#595](https://gitlab.haskell.org//ghc/ghc/issues/595), GHC's overlapping/non-exhaustive pattern checking is old and
|
|
crufty and misbehaves with several GHC's extensions, notably GADTs. In this page
|
|
crufty and misbehaves with several GHC's extensions, notably GADTs. In this page
|
|
we describe the problem and the algorithm we are currently implementing.
|
|
we describe the problem and the algorithm. It forms part of GHC 8.0.
|
|
|
|
|
|
|
|
**Performance related tickets** (to be solved for 8.0):
|
|
|
|
|
|
Background:
|
|
- [\#11160](https://gitlab.haskell.org//ghc/ghc/issues/11160)
|
|
|
|
- [\#11161](https://gitlab.haskell.org//ghc/ghc/issues/11161)
|
|
|
|
- [\#11162](https://gitlab.haskell.org//ghc/ghc/issues/11162)
|
|
|
|
- [\#11163](https://gitlab.haskell.org//ghc/ghc/issues/11163)
|
|
|
|
- [\#11195](https://gitlab.haskell.org//ghc/ghc/issues/11195)
|
|
|
|
- [\#11276](https://gitlab.haskell.org//ghc/ghc/issues/11276)
|
|
|
|
|
|
|
|
**Background**:
|
|
|
|
|
|
- The paper on which the previous approach were based [ Two techniques for compiling lazy pattern matching](http://moscova.inria.fr/~maranget/papers/lazy-pats-derniere.ps.gz)
|
|
- The paper on which the previous approach were based [ Two techniques for compiling lazy pattern matching](http://moscova.inria.fr/~maranget/papers/lazy-pats-derniere.ps.gz)
|
|
- Peter Sestoft's paper for negative patterns [ ML's pattern matching compilation and partial evaluation](http://lambda.csail.mit.edu/~chet/papers/others/s/sestoft/sestoft96ml.pdf)
|
|
- Peter Sestoft's paper for negative patterns [ ML's pattern matching compilation and partial evaluation](http://lambda.csail.mit.edu/~chet/papers/others/s/sestoft/sestoft96ml.pdf)
|
|
|
|
|
|
|
|
**Our solution**
|
|
Our solution
|
|
|
|
|
|
|
|
- Our paper, describing the algorithm we implemented [ GADTs meet their match](http://people.cs.kuleuven.be/~george.karachalias/papers/p424-karachalias.pdf).
|
|
- Our paper, describing the algorithm we implemented [ GADTs meet their match](http://people.cs.kuleuven.be/~george.karachalias/papers/p424-karachalias.pdf).
|
|
- [PatternMatchCheckImplementation](pattern-match-check-implementation) talks about the implementation in GHC.
|
|
- [PatternMatchCheckImplementation](pattern-match-check-implementation) talks about the implementation in GHC.
|
|
|
|
|
|
|
|
**Related tickets** (ones that are closed are still useful examples in the wild; they were only closed as duplicates):
|
|
Related tickets (ones that are closed are still useful examples in the wild; they were only closed as duplicates):
|
|
|
|
|
|
|
|
- [\#29](https://gitlab.haskell.org//ghc/ghc/issues/29)
|
|
- [\#29](https://gitlab.haskell.org//ghc/ghc/issues/29)
|
|
- [\#322](https://gitlab.haskell.org//ghc/ghc/issues/322)
|
|
- [\#322](https://gitlab.haskell.org//ghc/ghc/issues/322)
|
... | @@ -46,14 +52,6 @@ Related tickets (ones that are closed are still useful examples in the wild; the |
... | @@ -46,14 +52,6 @@ Related tickets (ones that are closed are still useful examples in the wild; the |
|
- [\#10600](https://gitlab.haskell.org//ghc/ghc/issues/10600)
|
|
- [\#10600](https://gitlab.haskell.org//ghc/ghc/issues/10600)
|
|
- [\#10746](https://gitlab.haskell.org//ghc/ghc/issues/10746)
|
|
- [\#10746](https://gitlab.haskell.org//ghc/ghc/issues/10746)
|
|
|
|
|
|
|
|
|
|
Performance related tickets:
|
|
|
|
|
|
|
|
- [\#11160](https://gitlab.haskell.org//ghc/ghc/issues/11160)
|
|
|
|
- [\#11161](https://gitlab.haskell.org//ghc/ghc/issues/11161)
|
|
|
|
- [\#11162](https://gitlab.haskell.org//ghc/ghc/issues/11162)
|
|
|
|
- [\#11163](https://gitlab.haskell.org//ghc/ghc/issues/11163)
|
|
|
|
|
|
|
|
# The main problem we wish to solve
|
|
# The main problem we wish to solve
|
|
|
|
|
|
|
|
|
... | | ... | |