Ist diese simple rein funktionale Warteschlange gültig?

Question

Ich habe eine rein funktionelle Warteschlange in Lisp (Schema) wie folgt entwickelt:

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

verzögerungs Nachteile cons ähnlich ist, aber es unterbricht die Auswertung des Schwanzes, indem es in einer Schließ Einwickeln. Delay-append ähnlich (delay-append s t) hängt t an s durch rekursive Suspensionen des Tails an.

Folglich umschließt jede Enqueue eine Schicht des Verschlusses, so dass sie O (1) ergibt, jeder Peek erhält einfach einen Wert, der O (1) ergibt, und jede Ausqueuerei ruft einen Verschluss ab und bewertet ihn, der ihn zu O (1) macht.

Ich habe das anderswo nicht gesehen; Zum Beispiel ist in Okasakis rein funktionalen Datenstrukturen die einfachste Warteschlange eine Bankwarteschlange, die wesentlich komplizierter ist als diese und nur O (1) Enqueue, Peek und Dequeue amortisiert hat. Was mich verdächtig macht, dass meine Argumentation falsch ist.

Klingt diese Datenstruktur? Gibt es irgendwo eine Referenz?

Bearbeiten: Verzögerung-Nachteile ist die falsche Sache in Verzögerung-Append hier zu verwenden; Ich versuche eine Funktion wie ein Makro zu benutzen (Danke Will Ness).

Ich habe versucht, es zu korrigieren

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

verwenden, aber dies mit der API funktioniert nicht.

Answer 1

Erstens, delay-cons kann nicht eine Funktion sein. Es muss ein Makro sein. For instance,

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

arbeitet in MIT-Schema.

Aber Sie bekommen, um dieses von nicht mit delay-cons in Ihrem delay-append:

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

So OK es ist.

Wie für Komplexitäten ist delay-append nicht ohne Kosten. Es wird um die ursprüngliche Warteschlange gewickelt. Stellen Sie sich vor, es hätte 30 Elemente; dann fügst du 10 weitere hinzu, eins nach dem anderen. Jetzt ist das Original in 10 Schichten von delay-append eingewickelt, die navigiert werden müssen, um an jedem dieser 30 Elemente zu kommen (29 tatsächlich, wie der Kopf in die unmittelbare car, durch die delay-append herausgezogen wird). So für n -adaped, n -Verwendete Verwendung Muster, sieht es aus wie eine quadratische Komplexität.

Die klassische Abhandlung dieses Problems im Zusammenhang mit Haskell ist "Why are difference lists more efficient than regular concatenation?". Ihre delay-append ist ähnlich wie „normale Verkettung“ gibt:

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

---

Hier ist eine Illustration:

(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