Wolfram Research

Function Repository Resource:

FoldRightList

Source Notebook

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]:=
ResourceFunction["FoldRightList"][f, x, {a, b, c, d}]
Out[1]=

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

In[2]:=
ResourceFunction["FoldRightList"][Plus, 0, {a, b, c, d}]
Out[2]=

Cumulative powers:

In[3]:=
ResourceFunction["FoldRightList"][Power, 1, {a, b, c, d}]
Out[3]=

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

In[4]:=
ResourceFunction["FoldRightList"][f, {a, b, c, d}]
Out[4]=

Use the operator form of FoldRightList on one argument:

In[5]:=
ResourceFunction["FoldRightList"][f][{a, b, c, d}]
Out[5]=

Use the operator form of FoldRightList on two arguments:

In[6]:=
ResourceFunction["FoldRightList"][f][x, {a, b, c, d}]
Out[6]=

Scope (1) 

Perform a chain of cross products:

In[7]:=
ResourceFunction[
 "FoldRightList"][Cross, {{1, -1, 1}, {0, 1, 1}, {1, 1, -1}}]
Out[7]=

Generalizations and Extensions (4) 

The head need not be List:

In[8]:=
ResourceFunction["FoldRightList"][f, x, p[a, b, c, d]]
Out[8]=

Use Unevaluated to fold prior to evaluation:

In[9]:=
ResourceFunction["FoldRightList"][f, Unevaluated[1 + 2 + 3]]
Out[9]=

Hold and fold with Hold:

In[10]:=
ResourceFunction["FoldRightList"][Hold, Hold[1 + 1, 2 + 2, 3 + 3]]
Out[10]=

Fold to the left:

In[11]:=
ResourceFunction["FoldRightList"][f[#2, #1] &, Reverse[{a, b, c, d}]]
Out[11]=

Or equivalently:

In[12]:=
FoldList[f, {a, b, c, d}]
Out[12]=

Applications (6) 

Form alternating sums:

In[13]:=
ResourceFunction["FoldRightList"][Subtract, {a, b, c, d, e}]
Out[13]=

Form continued fractions:

In[14]:=
ResourceFunction["FoldRightList"][1/(#2 + #1) &, x, {a, b, c, d}]
Out[14]=

Build up a nested polynomial (Horner form):

In[15]:=
ResourceFunction["FoldRightList"][#1 + x #2 &, 0, {a, b, c, d}]
Out[15]=

Build up a binary tree:

In[16]:=
ResourceFunction["FoldRightList"][List, x, {a, b, c, d}]
Out[16]=

Form a sequence of function compositions:

In[17]:=
ResourceFunction["FoldRightList"][#1[#2] &, x, {a, b, c, d}]
Out[17]=

Compare to using FoldList to form right compositions:

In[18]:=
FoldList[#2[#1] &, x, {a, b, c, d}]
Out[18]=

Form compositions of subvalues:

In[19]:=
ResourceFunction["FoldRightList"][#2[#1] &, x, {a, b, c, d}]
Out[19]=

Properties and Relations (7) 

FoldRightList makes a list of length n+1:

In[20]:=
Length[ResourceFunction["FoldRightList"][f, x, Range[10]]]
Out[20]=

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

In[21]:=
ResourceFunction["FoldRightList"][f, x, {}]
Out[21]=

The resource function FoldRight gives the last element of FoldRightList:

In[22]:=
ResourceFunction["FoldRightList"][f, x, {a, b, c}]
Out[22]=
In[23]:=
ResourceFunction["FoldRight"][f, x, {a, b, c}]
Out[23]=

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

In[24]:=
ResourceFunction["FoldRightList"][f[#2] &, x, Range[5]]
Out[24]=
In[25]:=
NestList[f, x, 5]
Out[25]=

Compare FoldRightList to FoldList structurally:

In[26]:=
TreeForm[ResourceFunction["FoldRightList"][f, z, {a, b, c}], AspectRatio -> 1/2]
Out[26]=

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

In[27]:=
TreeForm[FoldList[f, z, {a, b, c}], AspectRatio -> 1/2]
Out[27]=

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

In[28]:=
ResourceFunction["FoldRightList"][f, x, {y}]
Out[28]=
In[29]:=
FoldList[f, x, {y}]
Out[29]=

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

In[30]:=
ResourceFunction["FoldRightList"][Echo[#1] &, z, {a, b, c}]
Out[30]=

Compare to FoldList:

In[31]:=
FoldList[Echo[#2] &, z, {a, b, c}]
Out[31]=

Possible Issues (2) 

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

In[32]:=
ResourceFunction["FoldRightList"][f, {}]
Out[32]=

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

In[33]:=
ResourceFunction["FoldRight"][f, {}]
Out[33]=

Elements are taken in reverse order:

In[34]:=
ResourceFunction["FoldRightList"][f, z, Hold[Echo[1], Echo[2], Echo[3]]]
Out[34]=

Compare to a typical recursive definition of foldr:

In[35]:=
foldr[f_, z_, _[]] := z;
foldr[f_, z_, h_[x_, xs___]] := f[x, foldr[f, z, h[xs]]];
In[36]:=
foldr[f, z, Hold[Echo[1], Echo[2], Echo[3]]]
Out[36]=

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

In[37]:=
ResourceFunction["FoldRightList"][Plus, 0, Range[$RecursionLimit + 1]] // Short
Out[37]=

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

In[38]:=
foldr[Plus, 0, Range[$RecursionLimit + 1]] // Short
Out[38]=

Neat Examples (1) 

Compute a four-fold bird fold for fun:

In[39]:=
ResourceFunction["FoldRightList"][
  ResourceFunction["BirdSay"][#2, #1] &, "neat", {Left, Top, Right, Bottom}] // Column
Out[39]=

Resource History

Related Resources

License Information