Является ли эта простая чисто функциональная очередь действительной?

Question

Я разработал чисто функциональную очередь в Лиспе (схема) следующим образом:

;Internal functions 
(define (delay-cons x s) 
    (cons x (lambda() s))) 
(define (delay-car s) 
    (car s)) 
(define (delay-cdr s) 
    ((cdr s))) 

(define (delay-append s t) 
    (if (null? s) 
     t 
     (delay-cons (delay-car s) (delay-append (delay-cdr s) t)))) 

;API 
(define (enqueue x q) (delay-append q (delay-cons x empty))) 
(define dequeue delay-cdr) 
(define peek delay-car) 
(define empty '()) 
(define empty? null?) 

задержки минусы похожи на минусы, но она приостанавливает оценку хвоста, окружив его закрытие. delay-append аналогично (delay-append s t) добавляет t к s рекурсивными подвесками хвоста.

Следовательно, каждая обводка обертывает один слой затвора, делая его O (1), каждый заглядывает, просто извлекает значение, создавая его O (1), и каждый dequeue извлекает и оценивает одно замыкание, делающее его O (1).

Я не видел этого в другом месте; например, в чистых функциональных структурах данных Окасаки простейшая очередь представляет собой очередность банкира, которая значительно сложнее, чем эта, и только амортизировала O (1) enqueue, peek и dequeue. Что вызывает у меня подозрение, что в моих рассуждениях есть ошибка.

Это структура данных звук? Есть ли здесь ссылка?

Редактировать: Задержки-минусы - это неправильная вещь для использования в delay-append here; Я пытаюсь использовать функцию как макрос (спасибо Will Ness).

Я попытался исправить это с помощью

(define (delay-append s t) 
    (if (null? s) 
     t 
     (cons (delay-car s) (lambda() (delay-append (delay-cdr s) t))))) 

, но это не работает с API.

Answer 1

Во-первых, delay-cons может не быть функцией. Это должен быть макрос. For instance,

(define-syntax s-cons 
    (syntax-rules() 
    ((s-cons h t) (cons h (lambda() t))))) 

работает в MIT Scheme.

Но обойти это не с использованием delay-cons в вашем delay-append:

(define (delay-append s t) 
    (if (null? s) 
     t 
     (cons (delay-car s) (lambda() (delay-append (delay-cdr s) t))))) 

Так это нормально.

Что касается сложностей, delay-append не является без стоимости. Он обматывает исходную очередь. Представьте, что у него было 30 элементов; то вы добавите еще 10, один за другим. Теперь оригинал обернут 10 слоями delay-append, которые должны быть перемещены, чтобы получить по каждому из этих 30 элементов (фактически, когда головка вытащена в непосредственный car, delay-append). Таким образом, для n -appended, n -обработанный шаблон использования, он выглядит как квадратичная сложность.

Классический трактат этой проблемы в контексте Haskell - «Why are difference lists more efficient than regular concatenation?». Ваш delay-append похож на «обычную конкатенацию» там:

[] ++ t = t 
s ++ t = (head s) : ((tail s) ++ t) 

---

Вот иллюстрация:

(define (wrap x) (cons x (lambda()()))) 
(define (decdr s) ((cdr s))) 
(define (app s t) (if (null? s) t 
        (cons (car s) (lambda() (app (decdr s) t))))) 

;; RIGHT NESTING 
(app (wrap 1) (app (wrap 2) (app (wrap 3) (wrap 4)))) == 

(app #A=#[1 . (\->())] 
    (app #B=#[2 . (\->())] 
      (app #C=#[3 . (\->())] #D=#[4 . (\->())]))) == 

(app #A# (app #B# 
       #E=#[3 . (\-> (app (decdr #C#) #D#) )] )) == 

(app #A# #F=#[2 . (\-> (app (decdr #B#) #E#))]) == 

#G=#[1 . (\-> (app (decdr #A#) #F#))]  ;; the return value 

;; NOW, (car #G#) is O(1), but what about (decdr #G#)? 

(decdr #G#) == (app (decdr #A#) #F#) 
      == (app() #F#) 
      == #F# ;; O(1) steps as well 

;; LEFT NESTING 

(app (app (app (wrap 1) (wrap 2)) (wrap 3)) (wrap 4)) == 

(app (app (app #D=#[1 . (\->())] #C=#[2 . (\->())]) 
      #B=#[3 . (\->())]) 
    #A=#[4 . (\->())]) == 

(app (app #E=#[1 . (\-> (app (decdr #D#) #C#))] #B#) #A#) == 

(app #F=#[1 . (\-> (app (decdr #E#) #B#))] #A#) == 

#G=#[1 . (\-> (app (decdr #F#) #A#))]  ;; the return value 

;; NOW, (car #G#) is O(1), but what about (decdr #G#)? 

(decdr #G#) == (app (decdr #F#) #A#) 
      == (app (app (decdr #E#) #B#) #A#) 
      == (app (app (app (decdr #D#) #C#) #B#) #A#) 
      == ... ;; O(N) steps, re-creating the left-nesting structure