Comment by xdavidliu

17 hours ago

it's not entirely true that it does the same thing: even if it gives the same result. For many programming languages, fold and map can only act on non-lazy data structures, so require O(N) memory for the data that needs to be folded over, while tail-recursive functions usually only use O(1) memory, even stack memory.

Notable exceptions to the above are python3 with generators, which I believe truly use O(1) memory with map and fold. Haskell has lists that are lazy by default, but if you fold or map over them, it still "forces the thunk" for each element and thus you still end up using O(N) memory.

4 comments

xdavidliu

mrkeen 8 hours ago

* I don't think you meant to compare forcing each element (as opposed to forcing the input or output data structures)

* If you did mean it that way, I doubt Python can avoid forcing each element that goes through its generators. (Without, say, thunking up each element manually or using a generator of generators, etc.)

Here is Haskell using a fold and a map. It does not force the input, the output, or each element:

  main =

    let lazyInput = zip ([1..] :: [Int])
                        (repeat (error "boom"))

        lazyOutput = foldr (:) [] lazyInput

    in print (sum (map fst (take 10_000_000 lazyOutput)))

  > 50000005000000
  > 9 MiB total memory in use
  > real 0m0.062s

munchler 14 hours ago

I would hope that most standard libraries are optimized to avoid this sort of waste as much as possible. In F#, for example, I know that the standard `map` and `fold` are implemented imperatively for maximum performance.

xdavidliu 16 minutes ago

I don't know F#, but even if that were true, I'm guessing you need a list of the data in memory in the first place in order to fold or map over. That's still a disadvantage, since with tail recursion you don't, and thus it takes O(1) memory total.

lgas 13 hours ago

...although list fusion often saves you if the thunks were going to be forced eventually anyway.