Albert Y. C. Lai wrote:
Note the code of merge:
merge cmp xs [] = xs
merge cmp [] ys = ys
merge cmp (x:xs) (y:ys) = ...
Suppose you re-order the first two lines, i.e., make it
merge cmp [] ys = ys
merge cmp xs [] = xs
merge cmp (x:xs) (y:ys) = ...
what will happen?
Oh, so the mergesort
Milos Hasan wrote:
import System.Random
import Data.List
randFloats :: [Float]
randFloats = randoms (mkStdGen 0)
main = print $ sum $ sort $ take 100 randFloats
Could it be that Data.List.sort is the culprit that uses O(n) stack
space here? If so, is this avoidable?
sum is not
OK, you convinced me that sort is not the problem. After all, last (f
100) overflows too, and last is a very innocent function.
I don't know how you found the size (or structure) of the thunks (I'm
not aware of a ghci functionality that can tell me that), could you let
me know?
Anyway,