4 ms·
> Edit: Actually, the Haskell version can be O(1) in memory as the front of the list can be garbage collected, while the C++ version is O(n) in memory. Do you
by sriku 11y ago
> Edit: Actually, the Haskell version can be O(1) in memory as the front of the list can be garbage collected, while the C++ version is O(n) in memory.
Do you expect the following code to run in constant space?
head (drop 1000000000 (let fibs = 0 : 1 : zipWith max fibs (tail fibs) in fibs))
Neither ghci nor ghc seems to run it in constant space.
- tome 11y agoThat's because the entries in fibs are thunks which become very large. This runs in constant space: zipWith' f (x:xs) (y:ys) = let r = f x y in r `seq` r : zipWith' f xs ys head (drop (10 ^ 9) (let fibs = 0 : 1 : zipWith max fibs (tail fibs) in fibs))