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