5

Ho sviluppato una coda puramente funzionale in Lisp (Schema) come segue:Questa coda simulata puramente funzionale è valida?

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

ritardo-cons è simile a svantaggi, ma sospende la valutazione della coda avvolgendolo in una chiusura. delay-append similarly (delay-append s t) aggiunge t a s mediante sospensioni ricorsive della coda.

Di conseguenza, ogni accodamento avvolge uno strato di chiusura, rendendolo O (1), ogni sbircia semplicemente recupera un valore che lo rende O (1), e ogni dequeue recupera e valuta una chiusura rendendola O (1).

Non l'ho visto altrove; ad esempio nelle strutture dati puramente funzionali di Okasaki, la coda più semplice è la coda di un banchiere, che è molto più complicata di questa, e ha solo ammodato O (1) accodamento, sbirciatina e dequota. Il che mi fa sospettare che ci sia un errore nel mio ragionamento.

Questa struttura dati è valida? C'è un riferimento per questo da qualche parte?

Modifica: delay-cons è la cosa sbagliata da utilizzare in delay-append qui; Sto cercando di utilizzare una funzione come una macro (grazie Will Ness).

ho cercato di correggerlo usando

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

ma questo non funziona con l'API.

+2

Forse si dovrebbe venire con asserzioni, test ed esempi per verificare quello che hai fatto.Soprattutto non è chiaro quale sia il "ritardo" che questo fornisce e quali siano i "delay-cons", dato che Scheme fa una valutazione * rigorosa *. –

+0

la modifica l'ha interrotta. prima era OK. –

+0

Grazie Will, lo ha fatto; Stavo cercando di compensare il fatto che i delay-cons fossero errati (stavo cercando di usare una funzione come una macro) - l'enqueue è O (N) come scritto. –

risposta

5

Primo, delay-cons può non essere una funzione. Deve essere una macro. For instance,

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

funziona in Schema MIT.

ma si ottiene intorno a questo non utilizzando delay-cons nella tua delay-append:

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

, è nella norma.

Per quanto riguarda le complessità, delay-append non è senza costi. Si avvolge attorno alla coda originale. Immagina di avere 30 elementi; poi ne aggiungi altri 10, uno per uno. Ora l'originale è avvolto in 10 strati di delay-append, che devono essere esplorati per ottenere ciascuno di questi 30 elementi (29 in realtà, poiché la testa viene estratta nell'immediato car, dal numero delay-append). Quindi, per n -appendiato, n - modello di utilizzo accodato, sembra una complessità quadratica.

Il trattato classico di questo problema nel contesto Haskell è "Why are difference lists more efficient than regular concatenation?". Il tuo delay-append è simile a "concatenazione regolare" c'è:

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

Ecco un esempio:

(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 
+1

Ok, in un certo senso capisco: ogni accodamento richiede un numero costante di operazioni, ma una coda di riacquisto deve scartare un intero livello di accodamenti per spingere il prossimo numero incorporato nella parte inferiore delle chiusure, quindi riavvolgetelo, quindi è O (N). –

+0

@EdwardRoss cf. tangenzialmente correlati http://ideone.com/Si5axU. È pura coda O (1) funzionale (nel semplice Haskell), ma * estrae * i suoi nuovi elementi invece di lasciarli spingerli sopra. –

Problemi correlati