Libraries for Vicare Scheme: streams examples pipeline

Another way in which streams promote modularity is enabling the use of many small procedures that are easily composed into larger programs, in the style of Unix pipelines, where streams are important because they allow a large dataset to be processed one item at a time. Bird and Wadler provide the example of a text formatter. Their example uses right–folds:

(define (stream-fold-right f base strm)
  (if (stream-null? strm)
      base
    (f (stream-car strm)
       (stream-fold-right f base
         (stream-cdr strm)))))

(define (stream-fold-right-one f strm)
  (stream-match strm
    [(x) x]
    [(x . xs)
     (f x (stream-fold-right-one f xs))]))

Bird and Wadler define text as a stream of characters, and develop a standard package for operating on text, which they derive mathematically (this assumes the line–separator character is a single #\newline):

(define (breakon a)
  (stream-lambda (x xss)
    (if (equal? a x)
        (stream-append (stream (stream)) xss)
      (stream-append
        (stream (stream-append
            (stream x) (stream-car xss)))
        (stream-cdr xss)))))

(define-stream (lines strm)
  (stream-fold-right
    (breakon #\newline)
    (stream (stream))
    strm))

(define-stream (words strm)
  (stream-filter stream-pair?
    (stream-fold-right
      (breakon #\space)
      (stream (stream))
      strm)))

(define-stream (paras strm)
  (stream-filter stream-pair?
    (stream-fold-right
      (breakon stream-null)
      (stream (stream))
      strm)))

(define (insert a)
  (stream-lambda (xs ys)
    (stream-append xs (stream a) ys)))

(define unlines
  (lsec stream-fold-right-one
    (insert #\newline)))

(define unwords
  (lsec stream-fold-right-one
    (insert #\space)))

(define unparas
  (lsec stream-fold-right-one
    (insert stream-null)))

These versatile procedures can be composed to count words, lines and paragraphs; the normalize procedure squeezes out multiple spaces and blank lines:

(define countlines
  (compose stream-length lines))

(define countwords
  (compose stream-length
           stream-concat
           (lsec stream-map words)
           lines))

(define countparas
  (compose stream-length paras lines))

(define parse
  (compose (lsec stream-map
             (lsec stream-map words))
           paras
           lines))

(define unparse
  (compose unlines
           unparas
           (lsec stream-map
             (lsec stream-map unwords))))

(define normalize (compose unparse parse))

More useful than normalization is text–filling, which packs as many words onto each line as will fit.

(define (greedy m ws)
  (- (stream-length
       (stream-take-while (rsec <= m)
         (stream-scan
           (lambda (n word)
             (+ n (stream-length word) 1))
           -1
           ws))) 1))

(define-stream (fill m ws)
  (if (stream-null? ws)
      stream-null
    (let* ([n (greedy m ws)]
           [fstline (stream-take n ws)]
           [rstwrds (stream-drop n ws)])
      (stream-append
        (stream fstline)
        (fill m rstwrds)))))

(define linewords
  (compose stream-concat
           (lsec stream-map words)))

(define textparas
  (compose (lsec stream-map linewords)
           paras
           lines))

(define (filltext m strm)
  (unparse (stream-map (lsec fill m) (textparas strm))))

(stream-for-each display
  (filltext n (file->stream filename)))

Though each operator performs only a single task, they can be composed powerfully and expressively. The alternative is to build a single monolithic procedure for each task, which would be harder and involve repetitive code. Streams ensure procedures are called as needed.

1.15.14.3 A pipeline of procedures