More lazy lists

As a follow up to my previous post, I want to look a bit more on my lazy lists in R.

The implementation I showed delays evaluation of some expressions, but not as much delayed as they could be. Well, at least not for list concatenation.

I had these implementations of concatenation and reversal:

reverse <- function(lst) {
  do_reverse <- function(lst) {
    result <- nil
    while (!is_nil(lst)) {
      result <- cons(car(lst), result)
      lst <- cdr(lst)
    }
    result
  }
  force(lst)
  lazy_thunk <- function(lst) {
    function() lst()
  }
  lazy_thunk(do_reverse(lst))
}

cat <- function(l1, l2) {
  do_cat <- function(l1, l2) {
    rev_l1 <- nil
    while (!is_nil(l1)) {
      rev_l1 <- cons(car(l1), rev_l1)
      l1 <- cdr(l1)
    }
    result <- l2
    while (!is_nil(rev_l1)) {
      result <- cons(car(rev_l1), result)
      rev_l1 <- cdr(rev_l1)
    }
    result
  }
  force(l1)
  force(l2)
  lazy_thunk <- function(lst) {
    function() lst()
  }
  lazy_thunk(do_cat(l1, l2))
}

They delay evaluation but only of the first operation following them. For concatenation, we can actually delay evaluation a bit more such that all operations, concatenation and access to the concatenated list, can be done in constant time.

lazy_cat <- function(l1, l2) {
  force(l1)
  force(l2)
  first <- l1()
  if (is.null(first)) l2
  else {
    lazy_thunk <- function(lst) function() lst()
    lazy_thunk(cons(first$car, lazy_cat(first$cdr, l2)))
  }
}

microbenchmark(lst <- cat(l1, reverse(l2)), times = 1) # fast operation
microbenchmark(car(lst), times = 1) # slow operation -- needs to copy l1
microbenchmark(lst <- lazy_cat(l1, l2), times = 1) # fast operation
microbenchmark(car(lst), times = 1) # fast

We can use a similar trick for reversal, but we don’t gain much from it. We can implement lazy reversal as this:

lazy_reverse <- function(lst) {
  rev <- function(l, t) {
    force(l)
    force(t)
    first <- l()
    if (is.null(first)) t
    else {
      lazy_thunk <- function(lst) function() lst()
      lazy_thunk(rev(first$cdr, cons(first$car, t)))
    }
  }
  rev(lst, nil)
}

But the first time we access the head of a reversed list, we will still need to go all the way down the recursion. We cannot get the first element of the reversed list without going to the end of the original list. So in this case, the imperative solution I had before is actually still better—plus, it won’t run out of stack space with too deep recursions, which could easily happen with the lazy version.

Author: Thomas Mailund

My name is Thomas Mailund and I am a research associate professor at the Bioinformatics Research Center, Uni Aarhus. Before this I did a postdoc at the Dept of Statistics, Uni Oxford, and got my PhD from the Dept of Computer Science, Uni Aarhus.

Leave a Reply