One thing that has really caught my attention as I learn more programming languages is the idea of generators or infinite sequences of values. Yes, infinite. Coming from R, that seems unlikely, but in at least several other languages, it’s entirely possible thanks to iterators and lazy evaluation.
I saw this video which solves a codewars challenge using an infinite list, which references this one on the same topic.
First, a diversion into recursion
In Haskell, one of the first exercises after “Hello, World!” people discover is the Fibonacci sequence, where the \(n^{\rm th}\) value is given by the sum of the two previous values. As a function, this can be written as
λ> fib 0 = 0
λ> fib 1 = 1
λ> fib n = fib (n-1) + fib (n-2)Essentially, fib(0) returns 0. fib(1) returns 1, and for any value n it
returns the (recursively defined) sum of the two previous values. This isn’t infinite
at all…
\[ \begin{align*} {\rm fib}(4) &= {\rm fib}(3) + {\rm fib}(2)\\ &= ({\rm fib}(2) + {\rm fib}(1)) + ({\rm fib}(1) + {\rm fib}(0))\\ &= {\rm fib}(1) + {\rm fib}(0) + {\rm fib}(1) + {\rm fib}(1) + {\rm fib}(0)\\ &= 1 + 0 + 1 + 1 + 0\\ &= 3 \end{align*} \]
We could write that in R as
fib <- function(n) {
if (n == 0) return(0)
if (n == 1) return(1)
fib(n - 1) + fib(n - 2)
}
fib(4)## [1] 3fib(8)## [1] 21This may come as a surprise to some - the function is defined in terms of itself and some base cases. This is entirely fine in R and Haskell as they’re lazily evaluated - nothing happens until a value is actually used. In R, this means that if an argument to a function isn’t used, it’s not evaluated at all
loud_func <- function() {
cat("HELLLOOOOO!!!\n")
}
stays_quiet <- function(f, g = loud_func()) {
f(c(1, 2, 3, 4))
}
stays_quiet(f = mean)## [1] 2.5Notice that although the argument g is the invocation of loud_func(), it’s never
evaluated because we don’t use it. If we did use it…
noisy <- function(f, g = loud_func()) {
g
f(c(1, 2, 3, 4))
}
noisy(sum)## HELLLOOOOO!!!## [1] 10So, in these languages, we can define a function recursively. Given the base case(s), these will eventually return just a number, so the computation will complete.
Instead of just adding the values together, we can create a sequence of values by concatenating the iterations together. Starting with data and working down to a base case is called “recursion”, while starting from a base case and building up a data structure is “corecursion”.
If we want a sequence of values that represents the Fibonacci numbers, we can use
fibs <- function(n) {
if (n == 0) return(0)
if (n == 1) return(1)
prev <- fibs(n - 1)
c(prev, sum(tail(prev, 2)))
}
fibs(10)## [1] 1 1 2 3 5 8 13 21 34 55What’s blown my mind recently is the concept of infinite data structures. If I defined some function that, instead of working down to a base case, just kept expanding, say, by concatenating with a larger number (corecursion), such as
inf_series <- function(x) {
c(x, inf_series(x + 1))
}Then, if I tried to evaluate inf_series(5) this would produce
c(5, inf_series(6))which would expand to
c(5, 6, inf_series(7))and so on… forever. Of course, R can’t keep going forever
inf_series(5)Error: C stack usage 7971732 is too close to the limitThis error comes about because each function in R is a “closure” which “encloses” its environment. The way R keeps track of that (and where it needs to return after returning from a function) is by adding “stack frames” each time it dives deeper into a function calling a function. We’ve asked it to add infinity of these, so at some point it says “too many”.
Okay, so, not possible, right?
In Haskell I can define
λ> fibs = 0 : scanl (+) 1 fibswhich is a concatenation (:) of 0 with the result of scanl (+) 1 fibs. Note carefully,
this isn’t a function - it’s a vector of values defined recursively 🤯
To explain the definition a little more: scanl is similar to reduce in that it takes a starting value, a vector, and a
binary operator, but rather than reducing the vector to a value, it creates a new
vector with the successively reduced values. In this example, the values 1..5 are
successively added (+) to 0, so the second entry is 0+1=1, the next is 1+2=3, the
next is 3+3=6, then 6+4=10, then 10+5=15
λ> scanl (+) 0 [1..5]
[0,1,3,6,10,15]In the Fibonacci case, the operator is still addition, but the starting value is 1
and the vector is … the entire vector we’re defining. Writing out some of the
terms makes this easier to understand
λ> scanl (+) 1 [0, 1, 1, 2, 3, 5, 8]
[1,1,2,3,5,8,13,21]The first terms in the sequence, after concatenating with 0 will be
λ> [0, 1, 1, 2, 3, 5, 8]so, by defining fibs in terms of fibs, the sequence can go on forever. So,
what if you try to print this? In GHCI, the output will just stream forever, which
isn’t particularly useful. Instead, we can ask for some number of values, say, ten
λ> take 10 fibs
[0,1,1,2,3,5,8,13,21,34]Due to the laziness of Haskell, nothing is computed until it’s needed, so asking for any number of values is fast, despite the list being “infinite”
λ> take 100 fibs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,
17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,
3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,
165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,
4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,
86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,
1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,
17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,
190392490709135,308061521170129,498454011879264,806515533049393,
1304969544928657,2111485077978050,3416454622906707,5527939700884757,
8944394323791464,14472334024676221,23416728348467685,37889062373143906,
61305790721611591,99194853094755497,160500643816367088,259695496911122585,
420196140727489673,679891637638612258,1100087778366101931,1779979416004714189,
2880067194370816120,4660046610375530309,7540113804746346429,12200160415121876738,
19740274219868223167,31940434634990099905,51680708854858323072,
83621143489848422977,135301852344706746049,218922995834555169026]The idea of taking some values from an iterator shows up in other languages.
In Rust, I can create an infinite iterator of the value 1
use std::iter;
let ones = iter::repeat(1);and I can take some number of these, say, five, collected into a vector
ones.take(5).collect::<Vec<_>>()[1, 1, 1, 1, 1]Python also has a notion of infinite sequences, and they’re likely even more common.
When you work with a (regular, finite) list of values in a range, you get a range object
numbers = range(1, 9)
numbers## range(1, 9)type(numbers)## <class 'range'>You can convert this to a regular list with
list(numbers)## [1, 2, 3, 4, 5, 6, 7, 8]type(list(numbers))## <class 'list'>If you filter the numbers (which works on a range or a list) you get a filter object
even_numbers = filter(lambda x: x % 2 == 0, numbers)
even_numbers## <filter object at 0x7f5ac61da470>type(even_numbers)## <class 'filter'>which you can also convert to a list to see the values
list(even_numbers)## [2, 4, 6, 8]But, you can use this as an iterable, so you can get the ‘next’ value as many times as you need (defined here again to restart the iterator)
even_numbers = filter(lambda x: x % 2 == 0, numbers)
next(even_numbers)## 2next(even_numbers)## 4next(even_numbers)## 6next(even_numbers)## 8until there’s none left
next(even_numbers)## Error in py_call_impl(callable, dots$args, dots$keywords): StopIterationAs before, you can convert these to a fixed-length list, if desired
list(filter(lambda x: x % 2 == 0, numbers))## [2, 4, 6, 8]Still with me? Great. We can create an infinite list, if we want to, because it isn’t evaluated until we ask for elements
def infinitenumbers():
count = 0
while True:
yield count
count += 1
nums = infinitenumbers()
nums## <generator object infinitenumbers at 0x7f5ac615d310>type(nums)## <class 'generator'>This is a generator which means it’s capable of generating values. We can ask for as many as we want, now
next(nums)## 0next(nums)## 1next(nums)## 2next(nums)## 3next(nums)## 4If we want to convert some number of these to a list, we need a new function, roughly
the equivalent of Haskell’s take, in order to extract these
from itertools import islice
nums = infinitenumbers()
list(islice(nums, 10))## [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]and as before, if we ask for more now, we get the next batch
list(islice(nums, 10))## [10, 11, 12, 13, 14, 15, 16, 17, 18, 19]So, can we do this at all in R? We can’t build an infinite data structure per se, but what if we use a recursive definition and just… stop when it’s recursed enough times?
I initially thought about hacking into functions with body() to keep track of this,
but we’ve already discussed something we can use - the stack frames! R keeps track of
how deep it’s recursed using these, and we can access that information with sys.calls(),
the help for which describes
.GlobalEnv is given number 0 in the list of frames. Each subsequent function evaluation increases the frame stack by 1.So, we can tell from inside a recursive function how deeply nested we currently are.
I wrote the following helper, named for the Haskell inspiration
take <- function(f, n, x = 1) {
current_depth <- length(sys.calls()) # Subtract 1 to exclude the current call,
# but add 1 to start at 1
# uncomment this line to watch the magic happen!
# cat("Current Stack Depth: ", current_depth, "\n")
if (current_depth >= n) {
return(f(x))
} else {
return(c(f(x), take(f, n, x + 1)))
}
}this checks length(sys.calls()) which starts at 1 the first time it’s called, and adds
1 every time we go deeper. So long as we haven’t reached the requested depth, it
combines the passed-in function evaluated at \(x + i\) with a new evaluation one level deeper.
When that reaches the requested depth, it returns the evaluated function, bubbling up the returned values so that we end up with a vector of \(n\) values
\[ [f(x), f(x+1), f(x+2), f(x+3), \dots, f(x+n-1)] \]
Neat idea, but does it work? We can’t pass in an actual infinite data structure, but we can pass a function that defines one
A (trivial) function that produces a number at each value of x is
numbers <- function(x) {
x
}If we pretend that’s a generator for every number, we can “take” some values from it
take(numbers, 5) [1] 1 2 3 4 5take(numbers, 10) [1] 1 2 3 4 5 6 7 8 9 10A more complicated recipe for an infinite list of numbers could be
g <- function(x) {
x + 1
}
take(g, 7)[1] 2 3 4 5 6 7 8take(g, 10) [1] 2 3 4 5 6 7 8 9 10 11Dealing with non-sequential numbers might be trickier… what if we want all the even numbers?
evens <- function(x) {
if(x %% 2 == 0) x else NULL
}
take(evens, 10) [1] 2 4 6 8 10No, that only checks the first 10 numbers. Instead,
evens <- function(x) {
x * 2
}
take(evens, 7) [1] 2 4 6 8 10 12 14take(evens, 10) [1] 2 4 6 8 10 12 14 16 18 20What about our original example?
fibs <- function(x) {
if (x == 0) return(0)
if (x == 1) return(1)
fibs(x - 1) + fibs(x - 2)
}
# 10 values, starting at 0
take(fibs, 10, x = 0) [1] 0 1 1 2 3 5 8 13 21 34# 10 values, starting at 1
take(fibs, 10, x = 1) [1] 1 1 2 3 5 8 13 21 34 55Or, if we want 12 values, starting at the 10th
take(fibs, 12, x = 10) [1] 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
I’d say that’s working quite nicely!!!
Some caveats to keep in mind, though…
Since we’re relying on a count of stack frames on top of .GlobalEnv, this take()
implementation won’t work nicely inside another function. In fact, since
{knitr} is already a few functions deep, it also doesn’t work in an Rmd file (including
this blog which is Rmd via {blogdown}). Not for use in production, but a fun
exercise to figure it out at all.
Is there a better way to achieve this take() functionality? Where do you use
infinite iterators/generators in R or another language? Spot an improvement that
I can make? I can be found on Mastodon or
use the comments below.
devtools::session_info()
## ─ Session info ───────────────────────────────────────────────────────────────
## setting value
## version R version 4.1.2 (2021-11-01)
## os Pop!_OS 22.04 LTS
## system x86_64, linux-gnu
## ui X11
## language (EN)
## collate en_AU.UTF-8
## ctype en_AU.UTF-8
## tz Australia/Adelaide
## date 2023-08-18
## pandoc 3.1.1 @ /usr/lib/rstudio/resources/app/bin/quarto/bin/tools/ (via rmarkdown)
##
## ─ Packages ───────────────────────────────────────────────────────────────────
## package * version date (UTC) lib source
## blogdown 1.17 2023-05-16 [1] CRAN (R 4.1.2)
## bookdown 0.29 2022-09-12 [1] CRAN (R 4.1.2)
## bslib 0.5.0 2023-06-09 [3] CRAN (R 4.3.1)
## cachem 1.0.8 2023-05-01 [3] CRAN (R 4.3.0)
## callr 3.7.3 2022-11-02 [3] CRAN (R 4.2.2)
## cli 3.6.1 2023-03-23 [3] CRAN (R 4.2.3)
## crayon 1.5.2 2022-09-29 [3] CRAN (R 4.2.1)
## devtools 2.4.5 2022-10-11 [1] CRAN (R 4.1.2)
## digest 0.6.33 2023-07-07 [3] CRAN (R 4.3.1)
## ellipsis 0.3.2 2021-04-29 [3] CRAN (R 4.1.1)
## evaluate 0.21 2023-05-05 [3] CRAN (R 4.3.0)
## fastmap 1.1.1 2023-02-24 [3] CRAN (R 4.2.2)
## fs 1.6.3 2023-07-20 [3] CRAN (R 4.3.1)
## glue 1.6.2 2022-02-24 [3] CRAN (R 4.2.0)
## here 1.0.1 2020-12-13 [1] CRAN (R 4.1.2)
## htmltools 0.5.6 2023-08-10 [3] CRAN (R 4.3.1)
## htmlwidgets 1.5.4 2021-09-08 [1] CRAN (R 4.1.2)
## httpuv 1.6.6 2022-09-08 [1] CRAN (R 4.1.2)
## jquerylib 0.1.4 2021-04-26 [3] CRAN (R 4.1.2)
## jsonlite 1.8.7 2023-06-29 [3] CRAN (R 4.3.1)
## knitr 1.43 2023-05-25 [3] CRAN (R 4.3.0)
## later 1.3.0 2021-08-18 [1] CRAN (R 4.1.2)
## lattice 0.21-8 2023-04-05 [4] CRAN (R 4.3.0)
## lifecycle 1.0.3 2022-10-07 [3] CRAN (R 4.2.1)
## magrittr 2.0.3 2022-03-30 [3] CRAN (R 4.2.0)
## Matrix 1.6-0 2023-07-08 [4] CRAN (R 4.3.1)
## memoise 2.0.1 2021-11-26 [3] CRAN (R 4.2.0)
## mime 0.12 2021-09-28 [3] CRAN (R 4.2.0)
## miniUI 0.1.1.1 2018-05-18 [1] CRAN (R 4.1.2)
## pkgbuild 1.4.0 2022-11-27 [1] CRAN (R 4.1.2)
## pkgload 1.3.0 2022-06-27 [1] CRAN (R 4.1.2)
## png 0.1-7 2013-12-03 [1] CRAN (R 4.1.2)
## prettyunits 1.1.1 2020-01-24 [3] CRAN (R 4.0.1)
## processx 3.8.2 2023-06-30 [3] CRAN (R 4.3.1)
## profvis 0.3.7 2020-11-02 [1] CRAN (R 4.1.2)
## promises 1.2.0.1 2021-02-11 [1] CRAN (R 4.1.2)
## ps 1.7.5 2023-04-18 [3] CRAN (R 4.3.0)
## purrr 1.0.1 2023-01-10 [1] CRAN (R 4.1.2)
## R6 2.5.1 2021-08-19 [3] CRAN (R 4.2.0)
## Rcpp 1.0.9 2022-07-08 [1] CRAN (R 4.1.2)
## remotes 2.4.2 2021-11-30 [1] CRAN (R 4.1.2)
## reticulate 1.26 2022-08-31 [1] CRAN (R 4.1.2)
## rlang 1.1.1 2023-04-28 [1] CRAN (R 4.1.2)
## rmarkdown 2.23 2023-07-01 [3] CRAN (R 4.3.1)
## rprojroot 2.0.3 2022-04-02 [1] CRAN (R 4.1.2)
## rstudioapi 0.15.0 2023-07-07 [3] CRAN (R 4.3.1)
## sass 0.4.7 2023-07-15 [3] CRAN (R 4.3.1)
## sessioninfo 1.2.2 2021-12-06 [1] CRAN (R 4.1.2)
## shiny 1.7.2 2022-07-19 [1] CRAN (R 4.1.2)
## stringi 1.7.12 2023-01-11 [3] CRAN (R 4.2.2)
## stringr 1.5.0 2022-12-02 [1] CRAN (R 4.1.2)
## urlchecker 1.0.1 2021-11-30 [1] CRAN (R 4.1.2)
## usethis 2.1.6 2022-05-25 [1] CRAN (R 4.1.2)
## vctrs 0.6.3 2023-06-14 [1] CRAN (R 4.1.2)
## xfun 0.40 2023-08-09 [3] CRAN (R 4.3.1)
## xtable 1.8-4 2019-04-21 [1] CRAN (R 4.1.2)
## yaml 2.3.7 2023-01-23 [3] CRAN (R 4.2.2)
##
## [1] /home/jono/R/x86_64-pc-linux-gnu-library/4.1
## [2] /usr/local/lib/R/site-library
## [3] /usr/lib/R/site-library
## [4] /usr/lib/R/library
##
## ─ Python configuration ───────────────────────────────────────────────────────
## python: /usr/bin/python3
## libpython: /usr/lib/python3.10/config-3.10-x86_64-linux-gnu/libpython3.10.so
## pythonhome: //usr://usr
## version: 3.10.12 (main, Jun 11 2023, 05:26:28) [GCC 11.4.0]
## numpy: /home/jono/.local/lib/python3.10/site-packages/numpy
## numpy_version: 1.24.1
##
## NOTE: Python version was forced by RETICULATE_PYTHON_FALLBACK
##
## ──────────────────────────────────────────────────────────────────────────────