Basic Examples (6) 

Perform a right fold on a list:

In[1]:=

Out[1]=

Get cumulative sums of the elements of a list beginning from the end:

In[2]:=

Out[2]=

Cumulative powers:

In[3]:=

Out[3]=

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

In[4]:=

Out[4]=

Use the operator form of FoldRightList on one argument:

In[5]:=

Out[5]=

Use the operator form of FoldRightList on two arguments:

In[6]:=

Out[6]=

Scope (1) 

Perform a chain of cross products:

In[7]:=

Out[7]=

Generalizations and Extensions (4) 

The head need not be List:

In[8]:=

Out[8]=

Use Unevaluated to fold prior to evaluation:

In[9]:=

Out[9]=

Hold and fold with Hold:

In[10]:=

Out[10]=

Fold to the left:

In[11]:=

Out[11]=

Or equivalently:

In[12]:=

Out[12]=

Applications (6) 

Form alternating sums:

In[13]:=

Out[13]=

Form continued fractions:

In[14]:=

Out[14]=

Build up a nested polynomial (Horner form):

In[15]:=

Out[15]=

Build up a binary tree:

In[16]:=

Out[16]=

Form a sequence of function compositions:

In[17]:=

Out[17]=

Compare to using FoldList to form right compositions:

In[18]:=

Out[18]=

Form compositions of subvalues:

In[19]:=

Out[19]=

Properties and Relations (7) 

FoldRightList makes a list of length n+1:

In[20]:=

Out[20]=

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

In[21]:=

Out[21]=

The resource function FoldRight gives the last element of FoldRightList:

In[22]:=

Out[22]=

In[23]:=

Out[23]=

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

In[24]:=

Out[24]=

In[25]:=

Out[25]=

Compare FoldRightList to FoldList structurally:

In[26]:=

Out[26]=

In both cases, each item in the list is a subtree of the next:

In[27]:=

Out[27]=

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

In[28]:=

Out[28]=

In[29]:=

Out[29]=

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

In[30]:=

Out[30]=

Compare to FoldList:

In[31]:=

Out[31]=

Possible Issues (2) 

FoldRightList[f,{}] evaluates to an empty list, without a last element:

In[32]:=

Out[32]=

Therefore, FoldRight[f,{}] is undefined:

In[33]:=

Out[33]=

Elements are taken in reverse order:

In[34]:=

Out[34]=

Compare to a typical recursive definition of foldr:

In[35]:=

In[36]:=

Out[36]=

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

In[37]:=

Out[37]=

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

In[38]:=

Out[38]=

Neat Examples (1) 

Compute a four-fold bird fold for fun:

In[39]:=

Out[39]=