Repeatedly applying a function

[This article was first published on Higher Order Functions, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

A colleague of mine sent me the following R question:

I have a function that takes a list and does some stuff to it and then returns
it. I then take that output and run it through the same function again. But I
obviously don’t want to repeatedly type the function out, because I want the
number of function replications to be a declared argument. I had little luck
with functionals, although they
seemed like an obvious choice.

It goes on to say that the solution should work in a magrittr pipeline, so that
will influence how we solve the problem. Namely, we want to write a
function that will transform a pipeline like:

<span class="n">x</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">some_function</span><span class="p">(</span><span class="n">args</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">some_function</span><span class="p">(</span><span class="n">args</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">some_function</span><span class="p">(</span><span class="n">args</span><span class="p">)</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">some_function</span><span class="p">(</span><span class="n">args</span><span class="p">)</span><span class="w">
</span>

into a one-liner like

<span class="n">x</span><span class="w"> </span><span class="o">%>%</span><span class="w"> 
  </span><span class="n">repeated</span><span class="p">(</span><span class="n">.reps</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">4</span><span class="p">,</span><span class="w"> </span><span class="n">some_function</span><span class="p">,</span><span class="w"> </span><span class="n">args</span><span class="p">)</span><span class="w">
</span>

Winding up a while loop

The solution is repeated function application with some book-keeping. We could
do this with a while-loop or even with recursion. Here’s the loop version.

<span class="n">repeated</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">.x</span><span class="p">,</span><span class="w"> </span><span class="n">.reps</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="c1"># A single, finite, non-negative number of repetitions
</span><span class="w">  </span><span class="n">assertthat</span><span class="o">::</span><span class="n">assert_that</span><span class="p">(</span><span class="w">
    </span><span class="nf">length</span><span class="p">(</span><span class="n">.reps</span><span class="p">)</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w">
    </span><span class="o">!</span><span class="nf">is.na</span><span class="p">(</span><span class="n">.reps</span><span class="p">),</span><span class="w">
    </span><span class="n">.reps</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="m">0</span><span class="p">,</span><span class="w">
    </span><span class="nf">is.finite</span><span class="p">(</span><span class="n">.reps</span><span class="p">))</span><span class="w">
  
  </span><span class="c1"># accept purrr-style formula functions
</span><span class="w">  </span><span class="n">.f</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">purrr</span><span class="o">::</span><span class="n">as_function</span><span class="p">(</span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
  
  </span><span class="c1"># 0 .reps
</span><span class="w">  </span><span class="n">value</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">.x</span><span class="w">

  </span><span class="k">while</span><span class="w"> </span><span class="p">(</span><span class="n">.reps</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="m">1</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="n">value</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">.f</span><span class="p">(</span><span class="n">value</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
    </span><span class="n">.reps</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">.reps</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="w">
  </span><span class="p">}</span><span class="w">

  </span><span class="n">value</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

We start with some basic input-checking on the number of repetitions.
assert_that() is like stopifnot(), but it spells out failures a little more
verbosely. (To be honest, I don’t like that about half of the function is for
checking the number of repetitions, but that’s how it goes…)

<span class="n">library</span><span class="p">(</span><span class="n">purrr</span><span class="p">)</span><span class="w">
</span><span class="n">add</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">y</span><span class="p">)</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">+</span><span class="w"> </span><span class="n">y</span><span class="w">

</span><span class="m">10</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">-1</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> Error: .reps not greater than or equal to 0
</span><span class="m">10</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">1</span><span class="o">:</span><span class="m">10</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> Error: length(.reps) not equal to 1
</span>

The next line uses purrr’s as_function(), so that we can also use
formula-based anonymous functions. Here are examples with named functions,
typical anonymous functions and formula-based anonymous functions.

<span class="c1"># Regular named function
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 3 4 5 6
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">5</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 11 12 13 14
</span><span class="w">
</span><span class="c1"># Conventional anonymous function
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1]  4  8 12 16
</span><span class="w">
</span><span class="c1"># Formula-based anonymous function
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">4</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">.x</span><span class="w"> </span><span class="o">*</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 16 32 48 64
</span><span class="w">
</span><span class="c1"># A weird kind of power tower!
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">4</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">.x</span><span class="w"> </span><span class="o">^</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1]          1      65536   43046721 4294967296
</span><span class="p">((((</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="p">)</span><span class="w"> </span><span class="o">^</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w"> </span><span class="o">^</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w"> </span><span class="o">^</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w"> </span><span class="o">^</span><span class="w"> </span><span class="m">2</span><span class="w">
</span><span class="c1">#> [1]          1      65536   43046721 4294967296
</span>

Because we are working in a pipeline, we expect the first argument to be some
data. If we apply a function 0 times to the data, it should return the data.
That’s why we set the value to the input before the loop.

<span class="c1"># 0 function-applications
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">0</span><span class="p">,</span><span class="w"> </span><span class="n">add</span><span class="p">,</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] 1 2 3 4
</span>

This function is built around a while-loop that ticks down every time the
function is applied. Generally, loops are not considered idiomatic R. I
certainly try to avoid writing loops in R because the language has built-in
functions that can abstract over a lot of iteration and the required
book-keeping. If we are iterating over a dimension of something, like
elements in a vector or columns in a data-frame, we can probably write a
loop-free version. But here we are not looping over structure—we are looping
through time! This is fundamentally different kind of problem than the kinds
are that solved by Map() or lapply(). That’s why we had to invent our own
higher-order function to handle this kind of iteration for us.

Drilling down with recursion

But we can make it loop-free, by torturing the code into recursion. Okay, it’s
not that bad. Here I break it up into an input-handling step which sets the
stage for the recursive function recursively_repeat().

<span class="n">rrrepeated</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">.x</span><span class="p">,</span><span class="w"> </span><span class="n">.reps</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="c1"># A single, finite, non-negative number of repetitions
</span><span class="w">  </span><span class="n">assertthat</span><span class="o">::</span><span class="n">assert_that</span><span class="p">(</span><span class="w">
    </span><span class="nf">length</span><span class="p">(</span><span class="n">.reps</span><span class="p">)</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w">
    </span><span class="o">!</span><span class="nf">is.na</span><span class="p">(</span><span class="n">.reps</span><span class="p">),</span><span class="w">
    </span><span class="n">.reps</span><span class="w"> </span><span class="o">>=</span><span class="w"> </span><span class="m">0</span><span class="p">,</span><span class="w">
    </span><span class="nf">is.finite</span><span class="p">(</span><span class="n">.reps</span><span class="p">))</span><span class="w">
  
  </span><span class="c1"># accept purrr-style formula functions
</span><span class="w">  </span><span class="n">.f</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="n">purrr</span><span class="o">::</span><span class="n">as_function</span><span class="p">(</span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
  
  </span><span class="n">recursively_repeat</span><span class="p">(</span><span class="n">.x</span><span class="p">,</span><span class="w"> </span><span class="n">.reps</span><span class="p">,</span><span class="w"> </span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
</span><span class="p">}</span><span class="w">

</span><span class="n">recursively_repeat</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">.x</span><span class="p">,</span><span class="w"> </span><span class="n">.reps</span><span class="p">,</span><span class="w"> </span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
  </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">.reps</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="m">0</span><span class="p">)</span><span class="w"> </span><span class="p">{</span><span class="w">
    </span><span class="n">.x</span><span class="w">
  </span><span class="p">}</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span><span class="w"> 
    </span><span class="n">recursively_repeat</span><span class="p">(</span><span class="n">.f</span><span class="p">(</span><span class="n">.x</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">),</span><span class="w"> </span><span class="n">.reps</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">1</span><span class="p">,</span><span class="w"> </span><span class="n">.f</span><span class="p">,</span><span class="w"> </span><span class="n">...</span><span class="p">)</span><span class="w">
    </span><span class="c1"># (It would be more correct to use `Recall()` so that renaming the function
</span><span class="w">    </span><span class="c1"># doesn't break this line... -- how's that for an R deep cut?)
</span><span class="w">  </span><span class="p">}</span><span class="w">
</span><span class="p">}</span><span class="w">
</span>

This is classic recursion. There are two branches. In the base case, when
there are zero repetitions, the work is done and we return the input In the
recursive case, we re-apply the function, take away one of the repetitions
and then try the recursion again—and again and again until we bottom out
and hit the base case.

This verion works like its buddy:

<span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">5</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">.x</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] -9 -8 -7 -6
</span><span class="m">1</span><span class="o">:</span><span class="m">4</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">rrrepeated</span><span class="p">(</span><span class="m">5</span><span class="p">,</span><span class="w"> </span><span class="o">~</span><span class="w"> </span><span class="n">.x</span><span class="w"> </span><span class="o">-</span><span class="w"> </span><span class="m">2</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] -9 -8 -7 -6
</span><span class="w">
</span><span class="n">echo</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="n">paste0</span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="s2">" ("</span><span class="p">,</span><span class="w"> </span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="s2">")"</span><span class="p">)</span><span class="w"> 
</span><span class="s2">"hello"</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="n">echo</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] "hello (hello) (hello (hello))"
</span><span class="s2">"hello"</span><span class="w"> </span><span class="o">%>%</span><span class="w"> </span><span class="n">rrrepeated</span><span class="p">(</span><span class="m">2</span><span class="p">,</span><span class="w"> </span><span class="n">echo</span><span class="p">)</span><span class="w">
</span><span class="c1">#> [1] "hello (hello) (hello (hello))"
</span>

The main drawback to the recursive version is its readability. I just find it
harder to take in compared to the loop version—at least for a problem this
simple. For more interesting data structures, the recursive version may prove
more elegant and comprehensible.

A minor drawback to the recursive approach is its performance. It’s a little
slower at the median level than the loop approach.

<span class="n">shuffle</span><span class="w"> </span><span class="o"><-</span><span class="w"> </span><span class="k">function</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w"> </span><span class="n">sample</span><span class="p">(</span><span class="n">x</span><span class="p">)</span><span class="w">

</span><span class="n">microbenchmark</span><span class="o">::</span><span class="n">microbenchmark</span><span class="p">(</span><span class="w">
  </span><span class="n">with_while</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">repeated</span><span class="p">(</span><span class="m">1</span><span class="o">:</span><span class="m">100</span><span class="p">,</span><span class="w"> </span><span class="m">100</span><span class="p">,</span><span class="w"> </span><span class="n">shuffle</span><span class="p">),</span><span class="w">
  </span><span class="n">with_recur</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">rrrepeated</span><span class="p">(</span><span class="m">1</span><span class="o">:</span><span class="m">100</span><span class="p">,</span><span class="w"> </span><span class="m">100</span><span class="p">,</span><span class="w"> </span><span class="n">shuffle</span><span class="p">),</span><span class="w">
  </span><span class="n">times</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="m">1000</span><span class="w">
</span><span class="p">)</span><span class="w">
</span><span class="c1">#> Unit: microseconds
#>        expr     min        lq     mean   median       uq      max neval
#>  with_while 699.331  875.6795 1515.112 1093.551 1589.706 48083.54  1000
#>  with_recur 805.234 1037.1000 1796.680 1342.445 2011.684 13889.58  1000
#>  cld
#>   a 
#>    b
</span>

But I don’t usually worry about performance unless I can notice the computation
taking time.

What I will always notice is R trying to protect me from infinite
recursion when I crank up the number of repetition:

<span class="n">repeated</span><span class="p">(</span><span class="m">1</span><span class="o">:</span><span class="m">20</span><span class="p">,</span><span class="w"> </span><span class="m">1000</span><span class="p">,</span><span class="w"> </span><span class="n">shuffle</span><span class="p">)</span><span class="w">
</span><span class="c1">#>  [1] 12 14  2 17  7 19  4 10 13  1 20  9 15 11  6 16  5 18  8  3
</span><span class="n">rrrepeated</span><span class="p">(</span><span class="m">1</span><span class="o">:</span><span class="m">20</span><span class="p">,</span><span class="w"> </span><span class="m">1000</span><span class="p">,</span><span class="w"> </span><span class="n">shuffle</span><span class="p">)</span><span class="w">
</span><span class="c1">#> Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
</span>

To recap, we had a problem that centered around a specific kind of iteration:
repeatedly applying function on an input. To solve the problem, I wrote a
higher-order function to handle this kind of iteration. My first pass at the
problem used a simple while loop that ticked down a counter every time the
function was called. Dared by the loop-free purism, I also wrote a recursive
version, but for a problem this simple, it’s more of a curiousity.

To leave a comment for the author, please follow the link and comment on their blog: Higher Order Functions.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)