[Haskell-beginners] Merge Sort Stack Overflow

[Oscar Benjamin]

On 16 September 2013 19:39, Brandon Allbery <allbery.b at gmail.com> wrote:
> On Mon, Sep 16, 2013 at 2:34 PM, Oscar Benjamin <oscar.j.benjamin at gmail.com>
> 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