Czy ta prosta, funkcjonalna kolejka jest ważna?

Question

I rozwinęły czysto funkcjonalnego kolejki w Lisp (schemat) w następujący sposób:

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

opóźniających przeciw-podobna do wad, ale zawiesza oceny ogona przez owijanie go w zamknięciu. delay-append podobnie (delay-append s t) dodaje t do s przez rekurencyjne zawieszenie ogona.

W konsekwencji każda kolejka zawija jedną warstwę zamknięcia, co sprawia, że ​​O (1), każdy widok po prostu pobiera wartość powodującą, że jest O (1), a każda kolejka usuwa i ocenia jedno zamknięcie, co powoduje, że O (1).

Nie widziałem tego gdzie indziej; na przykład w czysto funkcjonalnych strukturach danych Okasaki najprostszą kolejką jest kolejka bankierska, która jest znacznie bardziej skomplikowana niż ta, i ma tylko zamortyzowaną O (1), podgląd i usunięcie kolejki. Co sprawia, że ​​podejrzewam, że w moim rozumowaniu jest błąd.

Czy ta struktura danych brzmi? Czy gdzieś tam jest odniesienie?

Edycja: opóźnienie-minusy to niewłaściwa rzecz do zastosowania w opóźnieniu-dopisz tutaj; Próbuję użyć funkcji podobnej do makra (dzięki Will Ness).

Próbowałem go skorygować za pomocą

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

ale to nie działa z API.

Answer 1

Po pierwsze, delay-cons może nie być funkcją. To musi być makro. For instance,

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

działa w programie MIT.

Ale to obejść przez nie wykorzystaniem delay-cons w swojej delay-append:

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

Więc to jest OK.

Jeśli chodzi o złożoności, delay-append nie jest bez kosztów. Zawija się wokół oryginalnej kolejki. Wyobraź sobie, że ma 30 elementów; następnie dodajesz kolejnych 10, jeden po drugim. Teraz oryginał jest zawinięty w 10 warstw delay-append, które muszą być nawigowane, aby uzyskać dostęp do każdego z tych 30 elementów (29 w rzeczywistości, gdy głowica jest wyciągnięta do natychmiastowego car, przez delay-append). W związku z tym, że dostępny wzór dostępu o nazwie n wygląda jak złożoność kwadratowa.

Klasycznym traktatem tego problemu w kontekście Haskell jest "Why are difference lists more efficient than regular concatenation?". Twój delay-append jest podobna do „regularnych konkatenacji” tam:

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

---

Oto ilustracja:

(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