Send Beginners mailing list submissions to
beginners@haskell.org
To subscribe or unsubscribe via the World Wide Web, visit
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
or, via email, send a message with subject or body 'help' to
beginners-requ...@haskell.org
You can reach the person managing the list at
beginners-ow...@haskell.org
When replying, please edit your Subject line so it is more specific
than "Re: Contents of Beginners digest..."
Today's Topics:
1. time complexity of pattern matching (Manikanda Krishnan)
2. Re: time complexity of pattern matching (Rahul Muttineni)
3. Re: time complexity of pattern matching (Manikanda Krishnan)
4. Re: time complexity of pattern matching (Rahul Muttineni)
5. Re: time complexity of pattern matching (Manikanda Krishnan)
----------------------------------------------------------------------
Message: 1
Date: Sat, 30 Jul 2016 12:55:11 +0530
From: Manikanda Krishnan <vmk8...@gmail.com>
To: Beginners@haskell.org
Subject: [Haskell-beginners] time complexity of pattern matching
Message-ID:
<cac_d3yukuk-y5sqr3pvncqgvuvbyp1fj3phwajsxjxfsq0y...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 . :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160730/1f890486/attachment-0001.html>
------------------------------
Message: 2
Date: Sat, 30 Jul 2016 13:09:06 +0530
From: Rahul Muttineni <rahulm...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] time complexity of pattern matching
Message-ID:
<CANij+eT0Lmo=3qmrfje8qv_wdsktfxjzh5gthhxfhk8l7ah...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <vmk8...@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@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-0001.html>
------------------------------
Message: 3
Date: Sat, 30 Jul 2016 13:49:16 +0530
From: Manikanda Krishnan <vmk8...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] time complexity of pattern matching
Message-ID:
<cac_d3yugk70lgdv_u57g4lku_zjwhq+fjz6k4vs5rscanho...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 :)
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160730/a37238e5/attachment-0001.html>
------------------------------
Message: 4
Date: Sat, 30 Jul 2016 14:09:44 +0530
From: Rahul Muttineni <rahulm...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] time complexity of pattern matching
Message-ID:
<canij+et5yotvqkmtmtobxebdsdd4wver1-pr8-c0jgvbu6c...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
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 <vmk8...@gmail.com>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160730/b939246b/attachment-0001.html>
------------------------------
Message: 5
Date: Sat, 30 Jul 2016 14:22:43 +0530
From: Manikanda Krishnan <vmk8...@gmail.com>
To: The Haskell-Beginners Mailing List - Discussion of primarily
beginner-level topics related to Haskell <beginners@haskell.org>
Subject: Re: [Haskell-beginners] time complexity of pattern matching
Message-ID:
<cac_d3yw0untkgnlj5wcnrce3bvajjy5q7g_gnvgxymfjt9k...@mail.gmail.com>
Content-Type: text/plain; charset="utf-8"
Thanks .
On Sat, Jul 30, 2016 at 2:09 PM, Rahul Muttineni <rahulm...@gmail.com>
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 <vmk8...@gmail.com>
> 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*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://mail.haskell.org/pipermail/beginners/attachments/20160730/dfb33b89/attachment.html>
------------------------------
Subject: Digest Footer
_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
------------------------------
End of Beginners Digest, Vol 97, Issue 15
*****************************************
