Basic Examples (6) 

Perform a right fold on a list:

In[1]:=

Out[1]=

Perform another right fold:

In[2]:=

Out[2]=

Use a right fold to form a power tower:

In[3]:=

Out[3]=

Use the last element of the list as the starting value:

In[4]:=

Out[4]=

Use the operator form of FoldRight on one argument:

In[5]:=

Out[5]=

Use the operator form of FoldRight on two arguments:

In[6]:=

Out[6]=

Scope (1) 

Perform a chain of cross products:

In[7]:=

Out[7]=

Generalizations and Extensions (2) 

The head need not be List:

In[8]:=

Out[8]=

Fold to the left:

In[9]:=

Out[9]=

Or equivalently:

In[10]:=

Out[10]=

Applications (5) 

Form an alternating sum:

In[11]:=

Out[11]=

Form a continued fraction:

In[12]:=

Out[12]=

Form a binary tree:

In[13]:=

Out[13]=

FoldRight can be used to perform composition:

In[14]:=

Out[14]=

Or equivalently:

In[15]:=

Out[15]=

Similarly, Fold can be used to form a right composition:

In[16]:=

Out[16]=

In[17]:=

Out[17]=

Form a composition of subvalues:

In[18]:=

Out[18]=

Properties and Relations (5) 

Folding with an empty list does not apply the function at all:

In[19]:=

Out[19]=

Functions that ignore their first argument give the same result as Nest:

In[20]:=

Out[20]=

In[21]:=

Out[21]=

Compare FoldRight to Fold structurally:

In[22]:=

Out[22]=

In[23]:=

Out[23]=

The order of arguments passed to f are reversed compared to Fold:

In[24]:=

Out[24]=

In[25]:=

Out[25]=

FoldRight takes elements starting on the right of the given list:

In[26]:=

Compare to Fold:

In[27]:=

Possible Issues (2) 

An empty list cannot be folded:

In[28]:=

Out[28]=

Elements are taken in reverse order:

In[29]:=

Out[29]=

Compare to a typical recursive definition of foldr:

In[30]:=

In[31]:=

Out[31]=

This implementation allows FoldRight to be tail recursive, which is far more efficient with respect to stack size:

In[32]:=

Out[32]=

Without tail recursion, the stack size would grow with respect to the size of the list:

In[33]:=

Out[33]=