# List comprehensions

This program provides simple list comprehensions for Scheme.
syntax: [[(stream-of ]]*expr*[[ ]]*clause*[[ ...)]]
[[List-of]] provices the syntax of list comprehensions, which generate lists
by means of looping expressions. The result is a list of objects of the
type returned by *expr*. There are four types of *clause*s:
• [[(]]*var*[[ range ]]*first*[[ ]]*past*[[ []]*step*[[])]] —
Loop over the implicit list of numbers that contains *first* as its
first element and increments each succeeding element by *step*. The
list ends before *past*, which is not an element of the list. If
*step* is not given it defaults to [[1]] if *first* is less than
*past* and [[-1]] otherwise. *First*, *past* and *step*
may be of any numeric type; if any of *first*, *past* or *step*
are inexact, the length of the output list may differ from
[[(ceiling (- (/ (- ]]*past*[[ ]]*first*[[) ]]*step*[[) 1)]].
• [[(]]*var*[[ in ]]*list-expr*[[)]] — Loop over the
elements of *list-expr*, in order from the start of the list, binding
each element of the list in turn to *var*.
• [[(]]*var*[[ is ]]*expr*[[)]] — Bind *var* to the
value obtained by evaluating *expr*.
• [[(pred? ]]*expr*[[)]] — Include in the output list only those
elements *x* for which [[(pred? ]]*x*[[)]] is non-[[#f]].
The scope of *var*iables bound in the list comprehension is the clauses
to the right of the binding clause (but not the binding clause itself) plus
the result expression. When two or more generators are present, the loops
are processed as if they are nested from left to right; that is, the
rightmost generator varies fastest. If no generators are present, the
result of the list comprehension is a list containing the result expression;
thus, [[(list-of 1)]] produces the list [['(1)]].
Consider the example list comprehension shown below:
[[
(list-of (+ y 6)
(x in '(1 2 3 4 5))
(odd? x)
(y is (* x x)))
]]
The first clause is [[(x in '(1 2 3 4 5))]], where [[in]] is a keyword, [[x]]
is a binding variable, and [['(1 2 3 4 5)]] is a literal list (or an expression
evaluating to a list); the list comprehension will loop through [['(1 2 3 4 5)]],
binding each list element in turn to the variable [[x]], continuing through the
rest of the list comprehension.
The second clause is a predicate, [[(odd? x)]], which passes only those elements
which cause the predicate to be true. In this case, the loop which originally
had five elements will pass only three elements, 1, 3, and 5, to the remaining
elements of the list comprehension.
The third clause is [[(y is (* x x))]], which binds [[y]] to the value resulting
from the expression [[(* x x)]]. This binding is applied to three items in turn,
returning 1, 9, and 25.
Finally, the list comprehension returns the value [['(7 15 31)]], which is the
result of applying the result expression [[(+ y 6)]] to each of the three items
returned by the third clause.
That macro could be written several other ways. A [[range]] clause loops over
numeric sequences, so the [[in]] clause above could be rewritten as shown below;
note that the final argument of the [[range]] clause never appears, which is
useful in those frequent cases where you want to iterate from [[0]] to [[n-1]].
[[
(list-of (+ y 6)
(x range 1 6)
(odd? x)
(y is (* x x)))
]]
Yet another way to write that same comprehension uses a step size provided by the
user instead of a default step size of [[1]]:
[[
(list-of (+ y 6)
(x range 1 6 2)
(y is (* x x)))
]]
List comprehensions are computed using a recursive macro:
(define-syntax list-of
(syntax-rules (range in is)
((_ "aux" expr base)
(cons expr base))
((_ "aux" expr base (x range first past step) clauses ...)
(let ((more? (if (positive? step) < >)))
(let loop ((z first))
(if (more? z past)
(let ((x z))
(list-of "aux" expr (loop (+ z step)) clauses ...))
base))))
((_ "aux" expr base (x range first past) clauses ...)
(let* ((step (if (< first past) 1 -1))
(more? (if (positive? step) < >)))
(let loop ((z first))
(if (more? z past)
(let ((x z))
(list-of "aux" expr (loop (+ z step)) clauses ...))
base))))
((_ "aux" expr base (x in xs) clauses ...)
(let loop ((z xs))
(if (null? z)
base
(let ((x (car z)))
(list-of "aux" expr (loop (cdr z)) clauses ...)))))
((_ "aux" expr base (x is y) clauses ...)
(let ((x y))
(list-of "aux" expr base clauses ...)))
((_ "aux" expr base pred? clauses ...)
(if pred?
(list-of "aux" expr base clauses ...)
base))
((_ expr clauses ...)
(list-of "aux" expr '() clauses ...))))
The macro calls itself recursively, one level of recursion for each clause plus
a final level of recursion for the base case. The expansion of the first
sample list comprehension is shown below:
[[
(let loop ((z '(1 2 3 4 5)))
(if (null? z)
'()
(let ((x (car z)))
(if (odd? x)
(let ((y (* x x)))
(cons (+ y 6) (loop (cdr z))))
(loop (cdr z))))))
]]
When this final expression is evaluated, the result is [['(7 16 31)]].