Function Repository Resource:

# FoldRight

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

## Version History

• 1.0.0 – 20 September 2019