模式匹配时间复杂度 Haskell

Question

我正在尝试了解模式匹配的时间复杂度。我认为 foo 中的匹配类型将花费恒定时间，而 bar 中的匹配模式将花费 O(n)，但我无法通过调试器逐步解决。

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

这个模式的时间复杂度是多少？

Answer 1

我用 -O2 编译了你的 bar 并生成了这个核心。评论是我的，并显示 compiler-generated 附加标识符的定义。

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

正如我们所见，编译器测试了第一个构造函数（[] vs :），然后是第二个，依此类推。它没有在同一个块中对同一个构造函数进行重复测试。

据我所知，Haskell 报告本身并未强制要求模式匹配具有特定的复杂性。由 Haskell 实现（例如 GHC）提供良好的优化水平。您可以期望 pattern-matching 以一种相当有效的方式编译，因为它是该语言最基本和普遍存在的结构之一。

要重现这一点，您可以使用 -O2 -ddump-simpl 进行编译并观察输出。

模式匹配时间复杂度 Haskell

Pattern Matching Time Complexity Haskell

haskell

pattern-matching