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?

  • 3
    $\begingroup$ Try executing TracePrint[Fold[f, a, Range[4]]]. $\endgroup$ Commented Aug 19, 2012 at 17:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – Ian Hincks
    Commented Aug 19, 2012 at 21:45

2 Answers 2


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];
MaxMemoryUsed[] //N



Fold[# + 1 &, big, Range@100];
MaxMemoryUsed[] //N


FoldList by comparison (with a much shorter Range):

FoldList[# + 1 &, big, Range@30];
MaxMemoryUsed[] //N


  • $\begingroup$ That's great, thanks! $\endgroup$
    – Ian Hincks
    Commented Aug 19, 2012 at 21:47

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.

  • 4
    $\begingroup$ 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. $\endgroup$ Commented Aug 19, 2012 at 19:38
  • $\begingroup$ Thanks for the implementation example R.M, but I was more looking for a test than an example. $\endgroup$
    – Ian Hincks
    Commented Aug 19, 2012 at 21:45
  • $\begingroup$ @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...) :) $\endgroup$
    – rm -rf
    Commented Aug 19, 2012 at 22:35
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 19, 2012 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.