#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): Replying to [comment:9 simonpj]:
Sounds complicated enough to be worth a Haskell Symposium paper! Seriously, writing a paper is often a good way to refine an idea.
Having that opportunity would be wonderful. I have to write it up with rigor for my undergrad thesis anyway. For a update on the progress: * I've put instrumentation code into GHC to extract patterns. * I've coded up a simplified version of the current algorithm outside of GHC. Simplifications are: * It only covers Constructor/Wildcard/Variable patterns. * It only selects a rhs but does no binding/the associated bookkeeping. * Record patterns with a different order then their definition are treated like a different constructor. * It treats all patterns as non-exhaustive. * I fully formulated my approach for matching the strictness of the current algorithm. The next steps are: * Implement my approach. * Get some statistics of their differences. * If it seems worthwhile try to measure the impact of the simplifier. (As the output of the desugar stage can be a lot worse and yet still result in perfect code). * Document the results in a presentable form. * Depending on how promising the results are hopefully implement the new approach in GHC. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14201#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler