On Sat, Jun 7, 2014 at 11:14 AM, Xiaojun "Phil" Hu
I found it relatively hard to reason about the time complexity of Haskell programs.
Is that the question you really want to ask? If it is, the answer is trivial: if it's O(f(n)) time in other languages, it's also O(f(n)) time in Haskell. (Note: space is a different story.) But what typically people want to know is: why is my program so slow? You wonder about the constants covered up by Big-Oh. And so you're going to have to get acquainted with 0) lambda calculus 1) graph reduction, 2) the G-machine, and 3) the spineless-tagless variant thereof. You're also going to have to learn to read Core and understand some of the higher order core-to-core optimizations that GHC performs. -- Kim-Ee