Haskell GHC: какова временная сложность сопоставления с N конструкторами? - PullRequest
Новая
       14

Haskell GHC: какова временная сложность сопоставления с N конструкторами?

34 голосов
/ 27 января 2012

Допустим, у нас есть следующий Haskell: 

data T = T0 | T1 | T2 | ... | TN

toInt :: T -> Int
toInt t = case t of
  T0 -> 0
  T1 -> 1
  T2 -> 2
  ...
  TN -> N

Какой алгоритм используется здесь для сопоставления с образцом? Я вижу два варианта:

(1) Линейный поиск, что-то вроде 

if      (t.tag == T0) { ... }
else if (t.tag == T1) { ... }
else ...

(2) Двоичный поиск, который был бы целесообразен в этой конкретной задаче: поиск t.tag в наборе {TO ... T1023}. Однако, если сопоставление с образцом в целом имеет много других возможностей и обобщений, это не может быть использовано.

Компиляция с GHC, какой алгоритм используется, и какова временная сложность с точки зрения N, для сопоставления с образцом на t в toInt?

1 Ответ

32 голосов
/ 27 января 2012

Используется таблица переходов, что делает сопоставление с шаблоном постоянной операцией.

К сожалению, я не могу найти актуальную цитату для этого, хотя эта страница упоминает реализацию операторов switch уровня Cmm в качестве таблиц переходов, а этот старый документ разработки тегов использует case для Bool в качестве примера, создавая таблицу переходов.

...