List Comprehensions in R

List comprehensions in Python or Haskell are popular and useful tools to filter a list given some predicates. The foreach package by Revolution Analytics gives us a handy interface to list comprehensions in R.

Quicksort is a recursive algorithm to sort a list. In Haskell, quicksort looks very clean and elegant using list comprehensions (from Learn You a Haskell for Great Good!):

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted

Quicksort takes the first element of a list and puts all smaller elements on the left of the item and all larger elements to the right. It recursively calls quicksort again on those sublists (smallerSorted and biggerSorted). The list comprehension [a | a <- xs, a < x] takes a list as an input and filters out all elements that are smaller than \(x\), whereas [a | a <- xs, a > x] filters out all elements that are larger than \(x\).

ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]  
[1,2,2,3,3,4,4,5,6,7,8,9,10]

Using foreach, the same algorithm in R looks like this (from the foreach vignette):

library(foreach)

qsort <- function(x) {
    n <- length(x)
    if (n == 0) {
        x
    } else {
        p <- sample(n, 1)
        smaller <- foreach(y=x[-p], .combine=c) %:% when(y <= x[p]) %do% y
        larger <- foreach(y=x[-p], .combine=c) %:% when(y > x[p]) %do% y
        c(qsort(smaller), x[p], qsort(larger))
    }
}

Not quite as concise as Haskell, but close!

> qsort(c(10,2,5,3,1,6,7,4,2,3,4,8,9))
[1]  1  2  2  3  3  4  4  5  6  7  8  9 10