A list builder or list accumulator

Question

Imagine a UTF-8 decoder that takes a list of bytes and returns human-readable code points like:

> (utf-8->human-readable-code-points '(32 32 195 160 160))
("u+0020" "u+0020" "u+00E0" ("Error: trailing byte without preceding start byte" 160))

This list builder functionality is meant for that function:

;; a list builder will allow us to build a list
;; by successively adding to the end without retracing
;; the list each time. And without having a stack of
;; cons calls to unwind. Will allow constructing a list
;; in order in a tail call fashion
;; (list-builder 'add! item) -- returns list so far
;; (list-builder 'list) -- returns list so far
(define (make-list-builder)
  (let [(list-under-construction '())
        (last-cons-cell '())]
    (lambda (dispatch . parameters)
      (case dispatch
        [(add!) (if (null? list-under-construction)
                   (begin
                     (set! list-under-construction (list (car parameters)))
                     (set! last-cons-cell list-under-construction))
                   (let ((new-cons-cell (list (car parameters))))
                     (set-cdr! last-cons-cell new-cons-cell)
                     (set! last-cons-cell new-cons-cell)))
         list-under-construction]
        [(list) list-under-construction]
        [else (error "unmatched dispatch" dispatch)]))))

Sample use:

> (define lb (make-list-builder))
> (lb 'list)
()
> (lb 'add! "here's an atom")
("here's an atom")
> (lb 'add! '(here's a list))
("here's an atom" (here 's a list))

Questions for review:

1. Is there a standard scheme function or way of doing this that I missed? The problem I am trying to ultimately solve can't be solved by a map because a map produces a list of the same size as the input, and map does not guarantee the order that elements of a Lisp or processed. Googling and searching Stack Overflow for scheme list builder or scheme list accumulater did not return useful results.

2. Is make-list-builder expressed in idiomatic Scheme?

3. How would you improve make-list-builder, or what would you do differently?

Answer 1

Wow, so sorry I missed seeing this question! (Normally I get emails when someone posts something tagged with scheme, but didn't see this one till now. :-()

So, the idiomatic way to build a list in Scheme is to cons elements to the front each time, then reverse the whole list at the end. This is still O(n) on the number of items to insert, so you're no worse off compared to the set-cdr! solution.

However, for this situation, a better solution (IMHO) in your case is actually to use unfold, which takes any given object (not necessarily a list) and results in a list. This is perfect for your situation because you are processing variable numbers of items in your input list at each step, which would make it a poor fit for map, fold, and the like (which processes exactly one item at each step).

Here's an example (require SRFIs 1, 8, and 60):

(define (decode-utf8 bytes)
  (define (invalid byte)
    (list 'invalid byte))
  (define (non-shortest val)
    (list 'non-shortest val))
  (define (end-of-input val)
    (list 'end-of-input val))

  (define (decode-start bytes)
    (define byte (car bytes))
    (define rest (cdr bytes))
    (cond ((< byte #x80) (values (integer->char byte) rest))
          ((< byte #xC0) (values (invalid byte) rest))
          ((< byte #xE0) (decode-rest 1 #x80 (logand byte #x1F) rest))
          ((< byte #xF0) (decode-rest 2 #x800 (logand byte #x0F) rest))
          ((< byte #xF8) (decode-rest 3 #x10000 (logand byte #x07) rest))
          (else (values (invalid byte) rest))))
  (define (decode-rest count minval val bytes)
    (cond ((zero? count) (values ((if (< val minval)
                                      non-shortest
                                      integer->char) val) bytes))
          ((null? bytes) (values (end-of-input val) bytes))
          (else
            (let ((byte (car bytes))
                  (rest (cdr bytes)))
              (cond ((< byte #x80) (values (invalid byte) rest))
                    ((< byte #xC0)
                     (decode-rest (- count 1) minval
                                  (+ (ash val 6) (logand byte #x3F))
                                  rest))
                    (else (values (invalid byte) rest)))))))

  (define (decode bytes)
    (receive (value rest) (decode-start bytes)
      value))
  (define (next bytes)
    (receive (value rest) (decode-start bytes)
      rest))

  (unfold null? decode next bytes))

The real action happens in decode-start and decode-rest, of course; both functions return two values:

1. the character decoded (or an error)
2. a reference to the next byte to process

The decode function extracts the first value, while next extracts the second.

---

If you still want to use a list builder, that's fine too. Here's a simple version: it builds the list when given no arguments, and otherwise appends the arguments given:

(define (make-list-builder)
  (define cur '())
  (case-lambda
   (() (reverse cur))
   ((item) (set! cur (cons item cur)))    ; redundant
   (items (set! cur (append-reverse items cur)))))

(where append-reverse comes from SRFI 1). Note that append-reverse with only one item is identical to cons, so the cons line above is redundant; it just demonstrates how you would do it if you want to add items one by one.

If you want to be able to send messages like in your version, here's how one might implement it:

(define (make-list-builder)
  (define cur '())
  (lambda (msg . args)
    (case msg
      ((add) (set! cur (append-reverse args cur)))
      ((get) (reverse cur))
      ((clear) (set! cur '())))))

In both cases, we keep track of a single variable only, not the start and end of list, because we are prepending elements rather than appending them.

---

There is still a valid use for the start-and-end approach you had, though: it's a common approach for implementing a queue. You enqueue by using the end reference, set-cdr!ing the new value in, then resetting the end reference; and of course, you dequeue by using the start reference. Here's an example (zero arguments means dequeue; otherwise enqueue the given arguments):

(define (make-queue)
  (define start (list 'queue-head))
  (define end start)
  (case-lambda
   (() (when (null? (cdr start))
         (error "empty queue"))
       (let ((result (cadr start)))
         (set-cdr! start (cddr start))
         (when (null? (cdr start))
           (set! end start))
         result))
   (items (set-cdr! end items)
          (set! end (last-pair end)))))

(here, last-pair comes from SRFI 1).