Komplexität der Musteranpassungszeit Haskell

Question

Ich versuche, die zeitliche Komplexität des Mustervergleichs zu verstehen. Ich dachte, das Abgleichen von Typen wie in foowürde eine konstante Zeit in Anspruch nehmen, während das Abgleichen von Mustern wie in barO (n) dauern würde, aber ich konnte es nicht herausfinden, indem ich Schritt für Schritt mit dem Debugger fortfuhr.

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

Was ist die zeitliche Komplexität dieser Muster?

Answer 1

Ich habe deine barmit kompiliert -O2und diesen Core generiert. Kommentare sind meine und zeigen die Definition für die vom Compiler generierten zusätzlichen Bezeichner.

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#
              }
              }
          }
      }

Wie wir sehen können, hat der Compiler den ersten Konstruktor ( []vs :), dann den zweiten und so weiter getestet . Es wurden keine wiederholten Tests desselben Konstruktors im selben Block durchgeführt.

Soweit ich weiß, schreibt der Haskell-Bericht selbst keine spezifische Komplexität für den Mustervergleich vor. Es liegt an der Haskell-Implementierung (z. B. GHC), ein gutes Maß an Optimierung bereitzustellen. Sie können davon ausgehen, dass Pattern Matching auf ziemlich effiziente Weise kompiliert wird, da es eines der grundlegendsten und allgegenwärtigsten Konstrukte der Sprache ist.

Um dies zu reproduzieren, können Sie -O2 -ddump-simpldie Ausgabe kompilieren und beobachten.