# Implementation of builtin function Fold

In the documentation for fold, it says

    Fold[f,x,list] gives the last element of FoldList[f,x,list].


But this is surely not the way it is implemented, right? In those cases where each step of the Fold returns a large object, it would be a huge waste of memory to actually store the whole list and then just pick the last element at the end.

How can I test this? Does Trace work as advertised, or does it skip printing intermediate steps sometimes?

-
Try executing TracePrint[Fold[f, a, Range[4]]]. –  Ｊ. Ｍ. Aug 19 '12 at 17:26
@NasserM.Abbasi: Sure, but I asked the question because in this case a piece of the internal implementation does matter; if it were done in one way, I would run out of RAM, and if it were done in another, I wouldn't. –  Ian Hincks Aug 19 '12 at 21:45

It's quite easy to show that Fold doesn't use the memory that would be required to store intermediate results.

$HistoryLength = 0; big = Range[1*^7]; ByteCount[big] MaxMemoryUsed[] //N  40000124 5.49458*10^7 Fold[# + 1 &, big, Range@100]; MaxMemoryUsed[] //N  1.34909*10^8 FoldList by comparison (with a much shorter Range): FoldList[# + 1 &, big, Range@30]; MaxMemoryUsed[] //N  2.49489*10^9 - That's great, thanks! – Ian Hincks Aug 19 '12 at 21:47 add comment You can implement Fold without having to create an intermediate list. The documentation probably mentions that just to make the relationship between Fold and FoldList clear. For example, consider this simple construction of a Fold operation: myFold[func_, x_, list_List] := Module[{f}, f[a_, l_List] /; Length@l >= 1 := f[f[a, First@l], Rest@l]; f[a_, {}] := a; f[x, list] /. f -> func ]  Now try it: myFold[f, a, {b, c, d}] (* f[f[f[a, b], c], d] *)  This is exactly what Fold would return. This and J. M.'s hint on TracePrint should make the implementation clear. - This implementation is nice conceptually, but has a serious flaw of not being tail-recursive. But, due to its clever scheme of first generating the expression in full and then evaluating, you fool the system so that it only requests to change the $IterationLimit (you basically construct a full but unevaluated call stack at once). The recursion is of course still there however, and when I try, e.g., Block[{\$IterationLimit = Infinity}, myFold[Drop, Range[100000], ConstantArray[1, {100000}]]], this silently blows the stack and crashes the kernel on my machine. –  Leonid Shifrin Aug 19 '12 at 19:38
Thanks for the implementation example R.M, but I was more looking for a test than an example. –  Ian Hincks Aug 19 '12 at 21:45
@LeonidShifrin Thanks for the detailed analysis. My intent was solely to show that Fold can be implemented without needing to build an explicit list and take the last element. I didn't even consider the concerns you raised (as is usual...) :) –  rm -rf Aug 19 '12 at 22:35
You are welcome :) I did not wish do diminish your code at all. But this is a first time I see such a "well-hidden" recursion, so I thought it would be useful to add a comment on its existence and dangers. Also, generally, I think that when we consider emulations of some built-in functions, it is always good to spell out all the differences. This both helps to understand the function in question better, and the limitations of the emulated version. –  Leonid Shifrin Aug 19 '12 at 22:49