Implementation of built-in function Fold

Question

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?

Answer 1

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

Answer 2

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.