Function Repository Resource:

# FoldRightList

Compute a right-associated fold returning the list of intermediate results

Contributed by: Richard Hennigan (Wolfram Research)
 ResourceFunction["FoldRightList"][f,x,{e1,…,en-1,en}] gives {x,f[en,x],f[en-1,f[en,x]],…}. ResourceFunction["FoldRightList"][f,{e1,…,en-2,en-1,en}] gives {en,f[en-1,en],f[en-2,f[en-1,en]],…}. ResourceFunction["FoldRightList"][f] represents an operator form of ResourceFunction["FoldRightList"] that can be applied to expressions.

## Details and Options

A right-associated fold is often called foldr.
With a length n list, ResourceFunction["FoldRightList"] generates a list of length n+1.
ResourceFunction["FoldRightList"][f,x,list] is effectively equivalent to FoldList[f[#2,#1]&,x,Reverse[list]].
ResourceFunction["FoldRightList"][f][list] is equivalent to ResourceFunction["FoldRightList"][f,list].
ResourceFunction["FoldRightList"][f][x,list] is equivalent to ResourceFunction["FoldRightList"][f,x,list].

## Examples

### 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]=

## Version History

• 1.0.0 – 20 September 2019