Pattern matching with streams in Racket?

Question

Pattern matching is a very readable alternative to manual destructuring in let clauses. I was wondering whether it's possible to use it with streams, like we can with lists.

As an illustration, consider a simple add-between implementation to produce a sequence with an element inserted between each of the elements of the original sequence.

(define (add-between lst sep)
  (match lst
    ['() '()]
    [(cons v vs)
     (cons v
           (cons sep
                 (add-between vs sep)))]))

Usage:

(add-between (list 'a 'b 'c) 'and) ; => '(a and b and c and)

What if we want to do the same with arbitrary sequences, like streams?

(define (add-between seq sep)
  (match seq
    ['() '()]
    [(cons v vs)
     (stream-cons v
                  (stream-cons sep
                               (add-between vs sep)))]))

This produces an error:

(add-between (stream 'a 'b 'c) 'and)
; match: no matching clause for #<stream>
; stdin:1:1
; Context:
;  /Applications/Racket v7.5/collects/racket/match/runtime.rkt:24:0 match:error
;  /Applications/Racket v7.5/collects/racket/repl.rkt:11:26

It would be ideal if we could pattern match on a generic sequence type, since that would encapsulate lists as well as streams.

Answer 1

You can define your own pattern-matching forms for streams, using define-match-expander, ? with predicates, and app with accessors.

#lang racket
(require syntax/parse/define (prefix-in * racket/stream))
(define (stream-empty? v) (and (stream? v) (*stream-empty? v)))
(define (stream-cons? v) (and (stream? v) (not (*stream-empty? v))))

(define-match-expander stream-cons
  (syntax-parser
    [(_ fst rst) #'(? stream-cons? (app stream-first fst) (app stream-rest rst))])
  (syntax-parser
    [(_ fst rst) #'(*stream-cons fst rst)]))

(define-match-expander stream*
  (syntax-parser
    [(_ rst) #'rst]
    [(_ fst more ... rst) #'(stream-cons fst (stream* more ... rst))])
  (syntax-parser
    [(_ init ... rst) #'(*stream* init ... rst)]))

(define-match-expander stream
  (syntax-parser
    [(_) #'(? stream-empty?)]
    [(_ elem ...) #'(stream* elem ... (? stream-empty?))])
  (syntax-parser
    [(_ elem ...) #'(*stream elem ...)]))

Using it:

> (define (add-between seq sep)
    (match seq
      [(stream) (stream)]
      [(stream-cons v vs)
       (stream-cons v
                    (stream-cons sep
                                 (add-between vs sep)))]))
> (add-between (stream 'a 'b 'c) 'and)
#<stream>
> (stream->list (add-between (stream 'a 'b 'c) 'and))
'(a and b and c and)

Answer 2

@AlexKnauth's answer is illuminating. I've since also discovered that the data/collection library provides a built-in way to do this for arbitrary sequences (that is, sequences as defined here). Using this match pattern, the code in the question could be written for generic sequences as:

(require data/collection)

(define (add-between seq sep)
  (match seq
    [(sequence) empty-stream]
    [(sequence v vs ...)
     (stream-cons v
                  (stream-cons sep
                               (add-between vs sep)))]))

Using it:

(sequence->list (add-between (stream 'a 'b 'c) 'and))
=> '(a and b and c and)

(sequence->string (add-between "hello" #\space))
"h e l l o "