Function Repository Resource:

FoldRight

Source Notebook

Compute a right-associated fold

Contributed by: Richard Hennigan (Wolfram Research)

ResourceFunction["FoldRight"][f,x,list]

gives the right-associated fold of f over the given arguments.

ResourceFunction["FoldRight"][f,list]

is equivalent to ResourceFunction["FoldRight"][f,Last[list],Most[list]].

ResourceFunction["FoldRight"][f]

represents an operator form of ResourceFunction["FoldRight"] that can be applied to expressions.

Details and Options

ResourceFunction["FoldRight"] is often called foldr.
ResourceFunction["FoldRight"][f,x,list] is effectively equivalent to Fold[f[#2,#1]&,x,Reverse[list]].
You can use Throw to exit from ResourceFunction["FoldRight"] before it is finished.
ResourceFunction["FoldRight"][f][list] is equivalent to ResourceFunction["FoldRight"][f,list].
ResourceFunction["FoldRight"][f][x,list] is equivalent to ResourceFunction["FoldRight"][f,x,list].

Examples

Basic Examples (6) 

Perform a right fold on a list:

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

Perform another right fold:

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

Use a right fold to form a power tower:

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

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

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

Use the operator form of FoldRight on one argument:

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

Use the operator form of FoldRight on two arguments:

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

Scope (1) 

Perform a chain of cross products:

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

Generalizations and Extensions (2) 

The head need not be List:

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

Fold to the left:

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

Or equivalently:

In[10]:=
Fold[f, {a, b, c, d}]
Out[10]=

Applications (5) 

Form an alternating sum:

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

Form a continued fraction:

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

Form a binary tree:

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

FoldRight can be used to perform composition:

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

Or equivalently:

In[15]:=
Composition[a, b, c, d][x]
Out[15]=

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

In[16]:=
Fold[#2[#1] &, x, {a, b, c, d}]
Out[16]=
In[17]:=
RightComposition[a, b, c, d][x]
Out[17]=

Form a composition of subvalues:

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

Properties and Relations (5) 

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

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

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

In[20]:=
ResourceFunction["FoldRight"][f[#2] &, x, Range[5]]
Out[20]=
In[21]:=
Nest[f, x, 5]
Out[21]=

Compare FoldRight to Fold structurally:

In[22]:=
TreeForm[ResourceFunction["FoldRight"][f, z, {a, b, c}], AspectRatio -> 1/2]
Out[22]=
In[23]:=
TreeForm[Fold[f, z, {a, b, c}], AspectRatio -> 1/2]
Out[23]=

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

In[24]:=
ResourceFunction["FoldRight"][f, x, {y}]
Out[24]=
In[25]:=
Fold[f, x, {y}]
Out[25]=

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

In[26]:=
ResourceFunction["FoldRight"][Print[#1] &, z, {a, b, c}]

Compare to Fold:

In[27]:=
Fold[Print[#2] &, z, {a, b, c}]

Possible Issues (2) 

An empty list cannot be folded:

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

Elements are taken in reverse order:

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

Compare to a typical recursive definition of foldr:

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

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

In[32]:=
ResourceFunction["FoldRight"][Plus, 0, Range[$RecursionLimit + 1]]
Out[32]=

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

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

Version History

  • 1.0.0 – 20 September 2019

Related Resources

License Information