Let's say we have the following Haskell:
data T = T0 | T1 | T2 | ... | TN
toInt :: T -> Int
toInt t = case t of
T0 -> 0
T1 -> 1
T2 -> 2
...
TN -> N
What algorithm is used to perform the pattern match here? I see two options:
(1) Linear search, something like
if (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...
(2) Binary search, which would be sensible in this specific task: searching for t.tag
in the set {TO
...T1023
}. However, where pattern matching in general has many other capabilities and generalizations, this may not be used.
Compiling with GHC, what algorithm is used, and what is the time complexity in terms of N, for pattern matching on t
in toInt
?
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With