In mailund/lc: List Comprehension

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>",
  fig.path = "man/figures/README-",
  out.width = "100%"
)

suppressPackageStartupMessages(library(lc, quietly = TRUE))
suppressPackageStartupMessages(library(magrittr, quietly = TRUE))
suppressPackageStartupMessages(library(pmatch, quietly = TRUE))

lc -- List comprehension in R

The goal of lc is to implement Haskell- and Python-like list comprehension in R. List comprehensions provide a syntax for mapping and filtering sequences. In R we would use functions such as Map or Filter, or the purrr alternatives, for this, but in languages such as Haskell or Python, there is syntactic sugar to make combinations of mapping and filtering easier to program.

Installation

You can install lc from GitHub with:

install.packages("devtools")
devtools::install_github("mailund/lc")

or from CRAN using

install.packages("lc")

Examples

Quick-sort

The algorithm quick-sort is based on the idea that to sort a list you pick a random element in it, called the pivot, split the data into those elements smaller than the pivot, equal to the pivot and larger than the pivot. Then sort those smaller and larger elements recursively and concatenate the three lists to get the final sorted list. One way to implement this in R is using the Filter function:

qsort <- function(lst) {
  n <- length(lst)
  if (n < 2) return(lst)

  pivot <- lst[[sample(n, size = 1)]]
  smaller <- Filter(function(x) x < pivot, lst)
  equal <- Filter(function(x) x == pivot, lst)
  larger <- Filter(function(x) x > pivot, lst)
  c(qsort(smaller), equal, qsort(larger))
}

(lst <- sample(1:10))
unlist(qsort(lst))

Using lc, you can implement the same algorithm like this:

qsort <- function(lst) {
  n <- length(lst)
  if (n < 2) return(lst)

  pivot <- lst[[sample(n, size = 1)]]
  smaller <- lc(x, x = lst, x < pivot)
  equal <- lc(x, x = lst, x == pivot)
  larger <- lc(x, x = lst, x > pivot)

  c(qsort(smaller), equal, qsort(larger))
}

(lst <- sample(1:10))
unlist(qsort(lst))

Eratosthenes sieve

The Eratosthenes sieve algorithm identifies the primes in the first n natural numbers by removing those elements that are divisible by smaller numbers. We can implement it using lc like this:

get_primes <- function(n) {
  not_primes <- lc(seq(from = 2*x, to = n, by = x), x = 2:sqrt(n)) %>% unlist %>% unique
  lc(p, p = 1:n, !(p %in% not_primes)) %>% unlist
}
get_primes(100)

Here, we create a list of all the non-primes first and then identifies the primes as those that are left. Alternatively, we can remove the non-primes iteratively while identifying the primes. For the implementation of this idea, we need to grow a list of primes. We don't want to do that using list, since this will give us a quadratic time algorithm, so I use the pmatch package to implement a linked list first:

library(pmatch)

linked_list := NIL | CONS(car, cdr : linked_list)

ll_length <- function(x, acc = 0) {
  cases(x,
        NIL -> acc,
        CONS(car,cdr) -> ll_length(cdr, acc + 1))
}
ll_to_list <- function(x) {
  y <- vector("list", length = ll_length(x))
  f <- function(x, i) {
    cases(x,
          NIL -> NULL,
          CONS(car, cdr) -> {
            y[[i]] <<- car
            f(cdr, i + 1)
        })
  }
  f(x, 1)
  y
}

The get_primes function can now be implemented like this:

get_primes <- function(n) {
  candidates <- 2:n
  primes <- NIL
  while (length(candidates) > 0) {
    p <- candidates[[1]]
    primes <- CONS(p, primes)
    candidates <- lc(x, x = candidates, x %% p != 0)
  }
  primes %>% ll_to_list %>% unlist %>% rev
}
get_primes(100)