Список Builder или список аккумулятор


Представьте, что в UTF-8 декодер, который принимает список байтов и возвращает удобочитаемое элементов кода, таких как:

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

Этот список функций строитель предназначен для этой функции:

;; 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)]))))

Используйте образец:

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

Вопросы для рассмотрения:

  1. Есть ли стандартная функция схема или способ сделать это, что я пропустил? Проблему я пытаюсь решить, в конечном счете, может быть решена с помощью карты, потому что карта выдает такой же размер, как входной сигнал, и карта не гарантирует того, что элементы шепелявит или обработанные. Погуглил и поиск переполнения стека, схемы список строителем или схема список accumulater не возвращает полезных результатов.

  2. Это сделать-список-строитель выразил в идиоматических схема?

  3. Как бы вы улучшили сделать-список-строитель, или что бы вы сделали иначе?



908
3
задан 27 августа 2011 в 08:08 Источник Поделиться
Комментарии
1 ответ

Вау, так жаль, что я пропустил этот вопрос! (Обычно я получаю письма, когда кто-то публикует что-то с тегами , но не видел этого до сих пор. :-()

Так, идиоматические способ, чтобы построить список в схеме есть минусы элементов на фронт каждый раз, затем поменять весь список в конце. Это все-таки за o(n) на количество элементов для вставки, так что вы не в худшем положении по сравнению с установлен-Уду! решение.

Но в такой ситуации, лучшее решение (ИМХО) в вашем случае фактически использовать развернется, которое занимает тот или иной объект (не обязательно список) и результаты в список. Это идеальный вариант для вашей ситуации, поскольку вы обрабатываете переменную число элементов во входном списке на каждом шаге, который сделал бы ее плохо подходят карты, фолд, и т. п. (который обрабатывает ровно один элемент на каждом шаге).

Вот пример (требуется SRFIs 1, 8, и 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))

Реальное действие происходит в декодирования-запуск и декодирование-остальные, конечно; обе функции возвращают два значения:


  1. символ декодируется (или ошибка)

  2. ссылка на следующий байт для обработки

В декодирования функция извлекает первое значение, в то время как следующий экстрактов второй.


Если вы все равно хотите использовать список, что тоже хорошо. Вот простой вариант: он строит список, когда не указано ни одного аргумента, а в противном случае добавляет аргументов:

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

(где добавить, обратной приходит из SRFI 1). Обратите внимание, что добавление-реверс с только один элемент идентичен минусы, так минусы строку выше избыточна; он просто демонстрирует, как вы могли бы сделать это, если вы хотите добавлять элементы по одному.

Если вы хотите иметь возможность отправлять сообщения как в вашей версии, вот как можно это реализовать:

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

В обоих случаях мы отслеживаем одной переменной, а не начало и конец списка, потому что мы добавляя элементы, а не добавлять их.


Есть еще действительный использовать для начального и конечного подход у вас, однако: это общий подход для реализации очереди. Вы поставит с помощью ссылок, набор-Уду!Инг новое значение, затем сброс конца отсчета; и конечно, вы удалять с помощью ссылки начать. Вот пример (ноль аргументов означает удалить, иначе поставит заданными аргументами):

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

(вот, последняя пара приходит с SRFI 1).

2
ответ дан 12 октября 2011 в 04:10 Источник Поделиться