Pattern Matching Time Complexity Haskell

Question

I'm trying to understand time complexity of pattern matching. I thought matching types like in foo would take constant time while matching patterns like in bar would take O(n) but I couldn't figure it out by going step-by-step with 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

What's the time complexity of this patterns?

user_3234959 · Answer

I compiled your bar with -O2 and generated this Core. Comments are mine, and show the definition for the compiler-generated additional identifiers.

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

As we can see, the compiler tested the first constructor ([] vs :) then the second, and so on. It did not perform repeated tests of the same constructor in the same block.

As far as I know, the Haskell Report itself does not mandate a specific complexity for pattern matching. It's up to the Haskell implementation (e.g., GHC) to provide a good level of optimization. You can expect pattern-matching to be compiled in a rather efficient way, given it's one of the most basic and ubiquitous constructs of the language.

To reproduce this, you can compile with -O2 -ddump-simpl and observe the output.

Pattern Matching Time Complexity Haskell

1 Answers