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

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.

Leave a Comment