lazylist

Lazy lists, or streams, are like lists but have delayed evaluation, allowing for the possibility of representing infinite sequences, among other things. This implementation is a direct translation of what is laid out in the book Structure and Interpretation of Computer Programs.

Basics

Create an empty stream using empty_stream(), or construct a new stream by attaching a head element to an existing stream using cons_stream:

library(lazylist)
empty_stream()
#> |   ...
cons_stream(1, empty_stream())
#> |   1 
#> |   ...

The tail of a stream is lazily evaluated, which allows for recursive definitions of infinite sequences:

integers_starting_from <- function(n) 
    cons_stream(n, integers_starting_from(n + 1))
integers <- integers_starting_from(1)
integers
#> |   1 
#> |   2 
#> |   3 
#> |   4 
#> |   5 
#> |   ...

Stream versions of the functionals map, accumulate, and filter are available:

# squares
stream_map(integers, function(x) x**2)
#> |   1 
#> |   4 
#> |   9 
#> |   16 
#> |   25 
#> |   ...

# running sub-total
stream_accumulate(integers, function(x, y) x + y, init = 0)
#> |   1 
#> |   3 
#> |   6 
#> |   10 
#> |   15 
#> |   ...

# only the evens:
stream_filter(integers, function(x) x%%2 == 0)
#> |   2 
#> |   4 
#> |   6 
#> |   8 
#> |   10 
#> |   ...

To access components of a stream, use stream_car (for the head) or stream_cdr (for the rest):

stream_car(integers)
#> [1] 1

stream_cdr(integers)
#> |   2 
#> |   3 
#> |   4 
#> |   5 
#> |   6 
#> |   ...

Examples/tutorials

To see how lazy lists can be useful in practice, see:

• Solving the 8-puzzle with lazy evaluation: uses lazily evaluated lists to implement A* search to find the shortest solution to a tile-puzzle.
• Lazy lists and branch-and-bound: uses lazy lists to implement a flexible branch-and-bound search to solve the knapsack problem
• Searching for Ramanujan's taxicab numbers: Using lazily evaluated lists to find integers that can be expressed as the sum of two cubes in two different ways, such as 1729 (which is 1³ + 12³ as well as 9³ + 10³)

Installation

You can install lazylist from github with:

# install.packages("devtools")
devtools::install_github("tarakc02/lazylist")