List comprehensions and pattern matching

Despite their simplicity, list comprehensions and pattern matching are
highly useful forms of syntactic sugar. List comprehensions perform
looping computations involving lists. Pattern matching destructures
lists, selecting alternatives and binding variables. Together, they
enable concise but highly-readable expressions for processing lists.
This note describes a simple implementation of list comprehensions and
pattern matching.

List comprehensions are provided by the list-of macro. The syntax
(list-of expr clause ...) produces a possibly-null list of objects of
the type returned by expr. There are four types of clauses:

- (var range first past [step]) -- Bind var to first, first + step,
..., until reaching past, which is not included in the output.
If step is not given, it defaults to 1 if (< first 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 variables 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. As a degenerate case, if
no generators are present, the result of a list comprehension is a
list containing the result expression; thus, (list-of 1) produces a
list containing only the element 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 the input 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 clauses of the list comprehension.

The third and final 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 list (7 15 31), which is
the result of applying the result expression (+ y 6) to each of the
three items returned by the final clause. The list-of macro expands
this expression into something you are probably glad you don't have
to write yourself:

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

That same list could be generated in 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)))

Another way to write that same comprehension uses a step size provided
by the user instead of the default step size of 1:

(list-of (+ y 6)
(x range 1 6 2)
(y is (* x x)))

List comprehensions are expanded by a macro that calls itself
recursively, one level of recursion for each clause plus a final level
of recursion for the base case. The complete implementation, which
is based on the set contructor in Kent Dybvig's book "The Scheme
Programming Language," is given below:

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

Pattern matching on lists is provided by the list-match macro. The
syntax (list-match expr clause ...) takes an input expr that evaluates
to a list. Clauses are of the form (pattern [fender] expr),
consisting
of a pattern that matches a list of a particular shape, an optional
fender that must succeed if the pattern is to match, and an expr that
is evaluated if the pattern matches. There are four types of
patterns:

- () -- Matches the null list.

- (pat0 pat1 ...) -- Matches a list with length exactly equal to the
number of pattern elements.

- (pat0 pat1 ... . patRest) -- Matches a list with length at least
as great as the number of pattern elements before the literal dot.
PatRest is a list containing the remaining elements of the input
list after the initial prefix of the list before the literal dot.

- pat -- Matches an entire list. Should always appear as the last
clause; it's not an error to appear elsewhere, but subsequent
clauses could never match.

Each pattern element may be:

- An identifier -- Matches any list element. Additionally, the
value of the list element is bound to the variable named by the
identifier, which is in scope in the fender and expr of the
corresponding clause. Each identifier in a single pattern must
be unique.

- A literal underscore -- Matches any list element, but creates no
bindings.

- A constant -- Matches if the expression equals the constant value,
but creates no bindings.

- A quote expression -- Matches if the expression equals the quote
expression, but creates no bindings.

- A quasiquote expression -- Matches if the expression equals the
quasiquote expression, but creates no bindings.

All comparisons are made with equal?. The patterns are tested in
order,
left to right, until a matching pattern is found; if fender is
present,
it must evaluate as non-#f for the match to be successful. Pattern
variables are bound in the corresponding fender and expression. Once
the matching pattern is found, the corresponding expr is evaluated and
returned as the result of the match. An error is signaled if no
pattern
matches the input list.

A simple match expression that computes the length of a list is given
below; the first pattern is the null list, which forms the base of the
recursion, and the second pattern matches a non-null input list, using
an underscore to signal that the value of the list element is not
bound in the result expression:

(define (len xs)
(list-match xs
(() 0)
((_ . xs) (+ 1 (len xs)))))

Fenders can test the common case where two list elements must be
identical; (unique eql? xs) casts out adjacent duplicates from an
input list:

(define (unique eql? xs)
(list-match xs
(() '())
((x) (list x))
((x y . rest) (eql? x y) (unique eql? (cons y rest)))
((x . rest) (cons x (unique eql? rest)))))

A more complex example uses two nested matchers to merge two input
lists ordered by the lt? predicate:

(define (list-merge lt? xx yy)
(list-match xx
(() yy)
((x . xs)
(list-match yy
(() xx)
((y . ys)
(if (lt? y x)
(cons y (list-merge lt? xx ys))
(cons x (list-merge lt? xs yy))))))))

Pattern matching is performed by a macro that expands into a cond
expression with one clause per pattern; an auxiliary macro handles the
various types of pattern elements. The complete implementation, which
is based on an idea of Jos Koot, is given below:

(define-syntax list-match
(syntax-rules ()
((_ expr (pattern fender ... template) ...)
(let ((obj expr))
(cond ((list-match-aux obj pattern fender ...
(list template)) => car) ...
(else (error 'list-match "pattern failure")))))))

(define-syntax list-match-aux
(lambda (stx)
(define (underscore? x)
(and (identifier? x) (bound-identifier=? x (syntax _))))
(syntax-case stx (quote quasiquote)
((_ obj pattern template)
(syntax (list-match-aux obj pattern #t template)))
((_ obj () fender template)
(syntax (and (null? obj) fender template)))
((_ obj underscore fender template)
(underscore? (syntax underscore))
(syntax (and fender template)))
((_ obj var fender template)
(identifier? (syntax var))
(syntax (let ((var obj)) (and fender template))))
((_ obj (quote datum) fender template)
(syntax (and (equal? obj (quote datum)) template)))
((_ obj (quasiquote datum) fender template)
(syntax (and (equal? obj (quasiquote datum)) fender
template)))
((_ obj (kar . kdr) fender template)
(syntax (and (pair? obj)
(let ((kar-obj (car obj)) (kdr-obj (cdr obj)))
(list-match-aux kar-obj kar
(list-match-aux kdr-obj kdr fender
template))))))
((_ obj const fender template)
(syntax (and (equal? obj const) fender template))))))

There are other systems that provide list comprehensions and pattern
matching. Sebastian Egner provides list comprehensions in SRFI-42.
Andrew Wright wrote a popular pattern matching package. And there are
others. But the list-of and list-match macros given above seem to hit
a sweet spot among possible list comprehensions and pattern matching;
they provide essential features, but avoid "feeping creaturitis."
They
are useful, and belong in every Scheme programmer's toolkit.

Phil
.

Relevant Pages

  • Re: destructuring-bind on infinite lists?
    ... Circular tree structures are banned from standard functions unless ... The description of destructuring semantics is split into two cases: ... in the pattern, there is also atom, quite possibly a different one, ... that infinite lists could be accepted: ...
    (comp.lang.lisp)
  • Re: Angle Brackets vs. foreach
    ... > I recently encountered a performance problem which was fixed by ... either a list of filenames or the next filename in the list is returned, ... @files will be used as a pattern to be globbed. ... then these values of @files will return the given lists when globbed using ...
    (comp.lang.perl.misc)
  • Other notes
    ... design goal in Python built-in data types is flexibility, ... are deques instead of lists with both amortised tail&tail operations? ... Pattern Matching programming paradigm of Mathematica. ... _ or Blankis a pattern object that can stand for any Mathematica ...
    (comp.lang.python)
  • Re: Help with spreadsheet
    ... I have standard patterns of cost over a period of time. ... Each pattern will be based upon a standard length of time. ... Col B is type of distribution ... I have a spreadsheet which lists a set of projects in column A ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Another @ Get command reference
    ... > automatically generates the commands that create lists. ... > FoxPro window, ... > on the current font. ... > If SHOW GETS is issued, the RANGE clause is re-evaluated. ...
    (microsoft.public.fox.helpwanted)