Correspondance de modèle Complexité temporelle Haskell

Question

J'essaie de comprendre la complexité temporelle de la correspondance de modèles. Je pensais que la correspondance des types comme dans fooprendrait un temps constant tandis que la correspondance des modèles comme dans barprendrait O (n) mais je ne pouvais pas le comprendre en procédant étape par étape avec le débogueur.

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

Quelle est la complexité temporelle de ces modèles?

Answer 1

J'ai compilé votre baravec -O2et généré ce Core. Les commentaires sont les miens et montrent la définition des identificateurs supplémentaires générés par le compilateur.

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

Comme nous pouvons le voir, le compilateur a testé le premier constructeur ( []vs :) puis le second, et ainsi de suite. Il n'a pas effectué de tests répétés du même constructeur dans le même bloc.

Autant que je sache, le rapport Haskell lui-même n'impose pas une complexité particulière pour l'appariement de modèles. C'est à l'implémentation Haskell (par exemple, GHC) de fournir un bon niveau d'optimisation. Vous pouvez vous attendre à ce que la correspondance de motifs soit compilée de manière assez efficace, étant donné que c'est l'une des constructions les plus basiques et les plus omniprésentes du langage.

Pour reproduire cela, vous pouvez compiler avec -O2 -ddump-simplet observer la sortie.