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?

It will take time depending on the pattern. For example [] will match in O(1), since it simply checks if the data constructor is []. For (x:[]), it will take two checks, first it will check if the outer data constructor is (:), and then that the second parameter is the []. For (1:x:xs) and (y:x:xs), it will also take two steps. So even if the list contains thousands of elements, it will not check all these elements. — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Sep 15, 2020 at 21:10
@WillemVanOnsem I understand that but I'm wondering that if it tries other patterns on top of the pattern until it arrives the matching pattern. If patterns are trivally enumerable like type constructors it might not need to. — bca
– bca, Commented Sep 15, 2020 at 21:12
The spec requires that the program act as if patterns were tested top-down, left-to-right. A compiler isn't restricted to checking in that order if it can determine the behavior would be unchanged. — Carl
– Carl, Commented Sep 16, 2020 at 0:32

chi · Accepted Answer · 2020-09-16 11:14:31Z

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.

Collectives™ on Stack Overflow

Pattern Matching Time Complexity Haskell

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related