Pattern Matching Time Complexity Haskell

Question

Sto cercando di capire la complessità temporale del pattern matching. Pensavo che la corrispondenza di tipi come in fooavrebbe richiesto tempo costante mentre la corrispondenza di modelli come in baravrebbe richiesto O (n) ma non sono riuscito a capirlo andando passo dopo passo con il debugger.

module Main where

data Foo = Bar | Baz | Cat

main :: IO ()
main =
  do
  print $ foo Baz line <- getLine let x = read line :: Int print $ bar [x,2,3]

-- Constructors of Foo known in advance 
-- So this can be a jump table
foo :: Foo -> Int
foo Bar = 1
foo Baz = 2
foo Cat = 3

-- Elements of list can't be known in advance
-- So this should take O(n) ???
bar :: [Int] -> Int
bar [] = 0
bar (x:[]) = 1
bar (1:x:xs) = 2
bar (y:x:xs) = 3

Qual è la complessità temporale di questi schemi?

Answer 1

Ho compilato il tuo barcon -O2e generato questo Core. I commenti sono miei e mostrano la definizione degli identificatori aggiuntivi generati dal compilatore.

bar
  = \ (ds_d35K :: [Int]) ->
      case ds_d35K of {
        [] -> Main.bar4;            -- GHC.Types.I# 0#
        : x_a13j ds1_d35U ->
          case ds1_d35U of {
            [] -> Main.bar3;        -- GHC.Types.I# 1#
            : ipv_s3na ipv1_s3nb ->
              case x_a13j of { GHC.Types.I# ds2_d35V ->
              case ds2_d35V of {
                __DEFAULT -> Main.bar2;  -- GHC.Types.I# 3#
                1# -> Main.bar1          -- GHC.Types.I# 2#
              }
              }
          }
      }

Come possiamo vedere, il compilatore ha testato il primo costruttore ( []vs :), poi il secondo e così via. Non ha eseguito test ripetuti dello stesso costruttore nello stesso blocco.

Per quanto ne so, lo stesso rapporto Haskell non impone una complessità specifica per il pattern matching. Spetta all'implementazione Haskell (ad esempio GHC) fornire un buon livello di ottimizzazione. Puoi aspettarti che il pattern-matching venga compilato in un modo piuttosto efficiente, dato che è uno dei costrutti più basilari e onnipresenti del linguaggio.

Per riprodurlo, puoi compilare -O2 -ddump-simple osservare l'output.