Haskell GHC: what is the time complexity of a pattern match with N constructors?

by

A jump table is used, making the pattern-match a constant time operation.

Unfortunately I’m unable to find an up-to-date citation for this, although this page mentions the implementation of Cmm-level switch statements as jump tables, and this old tagging design document uses a case on a Bool as an example, producing a jump table.

More Related Contents:

  1. Haskell: Parse error in pattern
  2. Pattern matching identical values
  3. Understanding the Haskell as-pattern
  4. Creating unique labels in Haskell
  5. Can I match a data constructor wildcard in Haskell?
  6. What is the difference between . (dot) and $ (dollar sign)?
  7. Good examples of Not a Functor/Functor/Applicative/Monad?
  8. Haskell ranges and floats
  9. Small Haskell program compiled with GHC into huge binary
  10. Multi-line commands in GHCi
  11. DatatypeContexts Deprecated in Latest GHC: Why?
  12. What does the exclamation mark mean in a Haskell declaration?
  13. Haskell function composition operator of type (c→d) → (a→b→c) → (a→b→d)
  14. Unwrapping a monad
  15. Haskell: Lists, Arrays, Vectors, Sequences
  16. How do I write, “if typeclass a, then a is also an instance of b by this definition.”
  17. Haskell read raw keyboard input
  18. Currying 3 Arguments in Haskell
  19. Applicative functor evaluation is not clear to me
  20. Expressing do block using only monadic bind syntax
  21. Defining a new monad in haskell raises no instance for Applicative
  22. What are Alternative’s “some” and “many” useful for?
  23. How to make a CAF not a CAF in Haskell?
  24. Check whether a type is an instance of Show in Haskell at runtime?
  25. Why is Haskell (sometimes) referred to as “Best Imperative Language”?
  26. Integral operators quot vs. div
  27. Converting IO Int to Int
  28. Haskell Constraint is no smaller than the instance head
  29. Is there, in Haskell, something similar to sub-guards?
  30. What is the Comonad typeclass in Haskell?

Leave a Comment