Re: [Haskell-beginners] Merge Sort Stack Overflow

On 16 September 2013 19:39, Brandon Allbery wrote:

On Mon, Sep 16, 2013 at 2:34 PM, Oscar Benjamin wrote:

...

I'm not sure how this gets optimised but your call-stack is

GHC's stack is a pattern match stack, *not* a call stack. While implementations are allowed to differ in how they produce non-strict evaluation, GHC uses graph reduction; "calls" are not necessarily done in the order you would expect in a procedural language.

Okay so I'm not so clear on the terminology that should be used for these things. My understanding is that lazy recursion over a list is fine in Haskell where it would be problematic in procedural languages, for example this function: timesTwo (x:xs) = 2*x:(timesTwo xs) recurses for every item in a list and could blow the stack for even small lists in a procedural language but is okay in Haskell. My understanding is that it's because it just evaluates whichever elements of the list are needed at the time so if you consume the list e.g. printing out the items then it never builds up any actual accumulating stack/heap of in-memory data during processing. However when you do this splitInHalf (x:y:xys) = (x:xs, y:ys) where (xs, ys) = splitInHalf xys and print out 1000s of values from one list and not the other then surely *something* has to build up in memory. How else would it remember which items belong in the other list? (This is what will happen when the OP tries to sort 500k random numbers since sqrt(500k) is roughly 1000.) Or am I still just not getting it? Oscar