[Haskell-cafe] Haskell maximum stack depth

[Adrian Hey]

Neil Mitchell wrote:
> Hi
> 
>> I have already partially scanned the list looking for the first
>> element that satisfies some condition, using a tail recursive search.
>>
>> If such an element is found I want to split the list at that point.
> 
> span/break? I really can't believe the memory overhead of span is that
> terrible, you are only duplicating the (:)'s and its only one
> traversal.
> 
>>> As an aside, my version of this function would be:
>>>
>>> neilGobbler :: Int -> [x] -> [x]
>>> neilGobbler n xs = length res `seq` res
>>>     where res = take n xs
>>>
>> My guess is it will use O(1) stack and burn O(n) heap (in addition that
>> actually used by the result), so assymptotic complexity wise same as
>> heapGobbler, but probably higher constant factors with ghc due to lazy
>> building of take thunks and subsequent reduction and indirection costs.
> 
> Sure? Guessing constant factors related to strictness and laziness is
> incredibly hard! My guess based on "gut feeling" is that the program
> will take less time, and use half the memory. But given my initial
> comment, that guess is not very reliable.

But the point is that *both* heapGobbler and neilGobbler are likely to
be slower and chew through at least twice as much heap as stackGobbler,
which would be the implementation of choice for both simplicity and
performance if it wasn't for this stack management problem.

Regards
--
Adrian Hey