#14201: Implement ideas from "Compiling Pattern Matching to Good Decision Trees" -------------------------------------+------------------------------------- Reporter: AndreasK | Owner: AndreasK Type: feature request | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.1 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by AndreasK): I realized I have no written anything about how to actually do this.\\ Nothing of this is set in stone yet but generally: To prevent additional strictness we can always limit argument evaluation to these columns which will be evaluated for any result (ignoring the possibility of pattern match failure). While we do have to compute that property for each column it should be able to do this while getting the data required to pick a good column. So I don't expect that to be too expensive. Preventing loss of strictness is a lot more expensive to calculate I fear. I also did not yet think much about how this impacts potential performance gains or how to optimize/implement it. So with this pretext here we go: Given a matrix of patterns based on your example {{{ A A A B _ C }}} My current idea is to associate constraints with each element starting without no constraints. If we chose column 2 we get on decomposition for C a matrix consisting only of `_`. However during matrix decomposition we check for constraints resulting from our selection and add these to the remaining matrix. In this case we would generate {Col1 != bot} for that entry.\\ When selecting a column we first have to resolve constraints associated with it. So while the resulting matrix has only a wildcard the constraint forces us the generate a case statement for the column ensuring the first parameter gets evaluated. Constraints are created by looking at the rows we eliminate based on the result we generate code for. But I have not yet formalized that to a degree where a detailed writeup on the specifics makes sense. While this is guaranteed to be more expensive then the current approach i hope to that performance gains as well as less work required by the simplifier makes up for it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14201#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler