In tarakc02/lazylist: Lazily Evaluated Lists

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "README-"
)

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())

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

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

# squares
stream_map(integers, function(x) x**2)

# running sub-total
stream_accumulate(integers, function(x, y) x + y, init = 0)

# only the evens:
stream_filter(integers, function(x) x%%2 == 0)

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

stream_car(integers)

stream_cdr(integers)

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^3 + 12^3$ as well as $9^3 + 10^3$)

Installation

You can install lazylist from github with:

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

tarakc02/lazylist documentation built on May 31, 2019, 3:51 a.m.