Haskell GHC: độ phức tạp về thời gian của một mẫu khớp với N constructors là bao nhiêu?

Question

Hãy nói rằng chúng tôi có những điều sau Haskell:

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

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

thuật toán nào được sử dụng để thực hiện các mô hình phù hợp đây? Tôi thấy hai lựa chọn:

(1) Tìm kiếm tuyến tính, một cái gì đó giống như

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

(2) tìm kiếm nhị phân, đó sẽ là hợp lý trong nhiệm vụ cụ thể sau: tìm kiếm t.tag trong tập {TO ... T1023}. Tuy nhiên, nơi khớp mẫu nói chung có nhiều khả năng và khái quát khác, điều này có thể không được sử dụng.

Biên dịch bằng GHC, thuật toán nào được sử dụng và độ phức tạp về thời gian theo N là gì, để khớp mẫu trên t trong toInt?

Answer 1

Bàn nhảy được sử dụng, làm cho mẫu khớp với thao tác thời gian không đổi.

Đáng tiếc là tôi không thể tìm thấy một up-to-date trích dẫn cho điều này, mặc dù this page đề cập đến việc thực hiện các Cmm cấp switch báo cáo như bảng nhảy, và this old tagging design document sử dụng một case trên Bool làm ví dụ, sản xuất một nhảy bảng.