Implementazione coda-ricorsiva di take-while

Question

Implementazione coda-ricorsiva di take-while

#1 da (2 voti)

4

Sto provando a scrivere un'implementazione ricorsiva della funzione take-while in Scheme (ma questo esercizio può essere fatto anche in un'altra lingua). Il mio primo tentativo è stato

(define (take-while p xs)
  (if (or (null? xs)
          (not (p (car xs))))
      '()
      (cons (car xs) (take-while p (cdr xs)))))

che funziona correttamente ma non è ricorsivo in coda. Il mio prossimo tentativo è stato

(define (take-while-tr p xs)
  (let loop ((acc '())
             (ys xs))
    (if (or (null? ys)
            (not (p (car ys))))
        (reverse acc)
        (loop (cons (car ys) acc) (cdr ys)))))

che è ricorsivo di coda ma ha bisogno di una chiamata a reverse come ultimo passaggio per restituire l'elenco dei risultati nell'ordine corretto.

Non riesco a trovare una soluzione che

è coda-ricorsivo,
non usa reverse ,
utilizza solo elenchi come struttura dei dati (utilizzando una struttura dati funzionale come Haskell's sequenza che consente di aggiungere elementi non è un'opzione),
ha una complessità lineare nella dimensione del prefisso, o almeno non ha una complessità quadratica (grazie a delnan per averlo indicato).

Esiste una soluzione alternativa che soddisfi tutte le proprietà di cui sopra? La mia intuizione mi dice che è impossibile accumulare il prefisso di una lista in modo ricorsivo in coda mantenendo l'ordine originale tra gli elementi (cioè senza la necessità di usare la retromarcia per regolare il risultato) ma non sono in grado di dimostrarlo .

Nota

La soluzione che utilizza reverse soddisfa le condizioni 1, 3, 4.

scheme algorithms list tail-call

posta Giorgio 03.06.2014 - 22:56

fonte

1 risposta

Leggi altre domande sui tag scheme algorithms list tail-call

Gestione dei percorsi delle risorse nel codice sorgente Sono vincolato dalla licenza di una libreria che viene utilizzata nel mio progetto ma non è distribuita con essa?

score 2 · Accepted Answer

Hmm, alcune continuazioni di intelligenza potrebbero funzionare

Per prima cosa scriviamo una funzione che ha una continuazione e restituisce una nuova continuazione che cons un valore sul risultato

(define cons-later
  (lambda (c x)
    (lambda (r)
      (cons x (c r)))))

Ora take-while

(define take-while
  (lambda (pred xs)
    (define worker
      (lambda (c xs)
        (if (pred (car xs))
            (worker (cons-later c (car xs)) ; Make our new continuation
                    (cdr xs))             
            (c '())))) ; Call the continuation

    (worker (lambda (x) x) xs)))

Tuttavia, a un certo punto paghiamo ancora il pifferaio; questa versione occupa un po 'più spazio rispetto al contrario.

Questo ovviamente usa le funzioni, ma dal momento che la tua implementazione inversa è stata ed è stata ancora contata come soddisfacente 1 3 e 4, farò semplicemente un fischio innocente.