[Haskell-beginners] time complexity of pattern matching

Rahul Muttineni rahulmutt at gmail.com
Sat Jul 30 08:39:44 UTC 2016


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 <vmk8993 at 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 at 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.html>


More information about the Beginners mailing list