<div dir="ltr"><div>Hi Manikanda,</div><div><br></div>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.<div><br></div><div>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.</div><div><br></div><div>A basic example:</div><div>---</div><div>data Color = Red | Blue | Green</div><div><br></div><div>isRed Red = True</div><div>isRed _ = False</div><div>---</div><div>GHC will transform this to</div><div>---</div><div>isRed x = case x of { Red -> True; DEFAULT -> False }</div><div>---</div><div>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.</div><div><br></div><div>Hope that helps!</div><div>Rahul Muttineni</div><div><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Sat, Jul 30, 2016 at 12:55 PM, Manikanda Krishnan <span dir="ltr"><<a href="mailto:vmk8993@gmail.com" target="_blank">vmk8993@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">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 .<div><br></div><div>Thanks in advance . :)</div></div>
<br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br></blockquote></div>
</div></div>