[Haskell-beginners] time complexity of pattern matching

[Rahul Muttineni]

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 <vmk8993 at gmail.com>
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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160730/f97456c2/attachment.html>