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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
