time complexity of pattern matching

Manikanda Krishnan

30 Jul 2016 30 Jul '16

3:25 a.m.

I am new to haskell and I have found it extremely interesting and somewhat addictive .I am curious to know about the time complexity of a pattern matching expression . Thanks in advance . :)

Attachments:

attachment.html (text/html — 241 bytes)

Show replies by date

Hi Manikanda, GHC does compilation by transformation and hence goes through a series of intermediate languages (like Core and STG) which are better suited for optimizations. Pattern matches are transformed into a sequence of case expressions. To answer you question, O(1) for simple patterns, but it really depends on the complexity of the pattern-matching expression and the Core-to-Core transformations that GHC applies. To truly understand the complexity, you need take a look at the Core/STG dump (I prefer STG since it's simple). If you have any particular code samples you'd like me to help you analyze, I'd be happy to do so. A basic example: --- data Color = Red | Blue | Green isRed Red = True isRed _ = False --- GHC will transform this to --- isRed x = case x of { Red -> True; DEFAULT -> False } --- You can think of a case as a switch expression in your standard imperative languages. A case expression will evaluate the thunk 'x' and perform a switch on the tag of the result. Each data constructor has an integer tag associated with it which will be the target of the switch. So the time complexity of `isRed` will be the time complexity of thunk evaluation which is impossible to predict because a thunk can be incredibly complex. Lazy evaluation is not so easy to analyze. It is highly context-sensitive. Hope that helps! Rahul Muttineni On Sat, Jul 30, 2016 at 12:55 PM, Manikanda Krishnan wrote:

...

I am new to haskell and I have found it extremely interesting and somewhat addictive .I am curious to know about the time complexity of a pattern matching expression .

Thanks in advance . :)

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

Manikanda Krishnan

4:19 a.m.

Thanks Rahul , I am currently only using simple patterns trying to replicate the behavior of standard functions that I have learned so far in order to familiarize myself with the recursive way of doing things . Currently I am just using the GHCI directive (:set +s) to compare runtimes etc and computing algorithmic complexity like how I normally do it in imperative languages (not sure if they hold up in lazy settings), Can you point me to resources where I can learn how the a)GHC actually works . b)optimize or analyze the code I write in haskell . Thanks in advance :)

Rahul Muttineni

4:39 a.m.

The way you're measuring algorithmic complexity does carry over to the lazy setting provided it's single-threaded because the order of execution is purely determined by the STG Code. In the concurrent lazy setting, it's a bit trickier since lightweight locking mechanisms occur when multiple threads evaluate the same thunk, making it non-deterministic. But the same problem is there for imperative concurrent programs. The best resources I've found on GHC are: Example-driven introduction to Core: https://davidterei.com/talks/2016-03-cs240h/ghc-compiler-slides.html GHC Illustrated (visual of the runtime system): https://takenobu-hs.github.io/downloads/haskell_ghc_illustrated.pdf Commentary: https://ghc.haskell.org/trac/ghc/wiki/Commentary *The Commentary is a bit out of date in some sections and very sparse, but that's the closest you can get on documented implementation details other than the Notes inside of the GHC source code itself. Beyond that, the GHC code base is your friend ;) But seriously though, a book on Haskell performance is long overdue. On Sat, Jul 30, 2016 at 1:49 PM, Manikanda Krishnan wrote:

...

Thanks Rahul ,

I am currently only using simple patterns trying to replicate the behavior of standard functions that I have learned so far in order to familiarize myself with the recursive way of doing things .

Currently I am just using the GHCI directive (:set +s) to compare runtimes etc and computing algorithmic complexity like how I normally do it in imperative languages (not sure if they hold up in lazy settings),

Can you point me to resources where I can learn how the a)GHC actually works . b)optimize or analyze the code I write in haskell .

Thanks in advance :)

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- Rahul Muttineni

Manikanda Krishnan

4:52 a.m.

Thanks . On Sat, Jul 30, 2016 at 2:09 PM, Rahul Muttineni wrote:

...

The way you're measuring algorithmic complexity does carry over to the lazy setting provided it's single-threaded because the order of execution is purely determined by the STG Code. In the concurrent lazy setting, it's a bit trickier since lightweight locking mechanisms occur when multiple threads evaluate the same thunk, making it non-deterministic. But the same problem is there for imperative concurrent programs.

The best resources I've found on GHC are:

Example-driven introduction to Core: https://davidterei.com/talks/2016-03-cs240h/ghc-compiler-slides.html GHC Illustrated (visual of the runtime system): https://takenobu-hs.github.io/downloads/haskell_ghc_illustrated.pdf Commentary: https://ghc.haskell.org/trac/ghc/wiki/Commentary *The Commentary is a bit out of date in some sections and very sparse, but that's the closest you can get on documented implementation details other than the Notes inside of the GHC source code itself.

Beyond that, the GHC code base is your friend ;) But seriously though, a book on Haskell performance is long overdue.

On Sat, Jul 30, 2016 at 1:49 PM, Manikanda Krishnan wrote:

...
Thanks Rahul ,

I am currently only using simple patterns trying to replicate the behavior of standard functions that I have learned so far in order to familiarize myself with the recursive way of doing things .

Currently I am just using the GHCI directive (:set +s) to compare runtimes etc and computing algorithmic complexity like how I normally do it in imperative languages (not sure if they hold up in lazy settings),

Can you point me to resources where I can learn how the a)GHC actually works . b)optimize or analyze the code I write in haskell .

Thanks in advance :)

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- Rahul Muttineni

_______________________________________________ Beginners mailing list Beginners@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners

-- Regards , *Manikanda Krishnan V*

3215

Age (days ago)

3215

Last active (days ago)

List overview

Download

4 comments

2 participants

participants (2)

Manikanda Krishnan
Rahul Muttineni