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.
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 *. –
la modifica l'ha interrotta. prima era OK. –
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. –