1.15.12 Matching

Syntax: stream-match stream clause ...

Provide the syntax of pattern–matching for streams. The input stream is an expression that evaluates to a stream. clause arguments are of the form:

(?pattern ?expr)
(?pattern ?fender ?expr)

consisting of a ?pattern that matches a stream 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 stream.

(pat0 pat1 ...)

Matches a finite stream with length exactly equal to the number of pattern elements.

(pat0 pat1 ... . patrest)

Matches an infinite stream, or a finite stream with length at least as great as the number of pattern elements before the literal dot.

pat

Matches an entire stream; should always appear last in the list of clauses; it’s not an error to appear elsewhere, but subsequent clauses could never match.

Each ?pattern element may be either:

An identifier

Matches any stream element; additionally, the value of the stream element is bound to the variable named by the identifier, which is in scope in the fender and expression of the corresponding clause; each identifier in a single pattern must be unique.

A literal underscore

Matches any stream element, but creates no bindings.

The patterns are tested in order, left–to–right, until a matching pattern is found; if ?fender is present, it must evaluate as true for the match to be successful. Pattern variables are bound in the corresponding fender and expression. Once the matching pattern is found, the corresponding expression is evaluated and returned as the result of the match. An error is signaled if no pattern matches the input stream.

stream-match is often used to distinguish null streams from non–null streams, binding head and tail:

(define (len strm)
  (stream-match strm
    (()                 0)
    ((head . tail)      (+ 1 (len tail)))))

Fenders can test the common case where two stream elements must be identical; the else pattern is an identifier bound to the entire stream, not a keyword as in cond.

(stream-match strm
  ((x y . _) (equal? x y)
   'ok)
  (else
   'error))

A more complex example uses two nested matchers to match two different stream arguments; (stream-merge lt? . strms) stably merges two or more streams ordered by the lt? predicate:

(define-stream (stream-merge lt? . strms)

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

  (stream-let loop ((strms strms))
    (cond ((null? strms)
           stream-null)
          ((null? (cdr strms))
           (car strms))
          (else
           (merge (car strms)
                  (apply stream-merge lt?
                  (cdr strms)))))))