Clojure: si può ripetere solo dalla posizione di coda

Question

Sto provando a invertire in modo ricorsivo una lista, ma sto ottenendo Can only recur from tail position sulla corsa. Cosa significa esattamente e come può essere migliorato il mio codice in modo che funzioni?

(defn recursive-reverse [coll] 
    (loop [coll coll] 
    (if (< (count coll) 2) '(coll) 
     (conj (first coll) (recur (rest coll))) 
    ))) 

EDIT

uscita per soluzione di Oscar. Funziona per le liste ma non per i vettori?

user=> (= (recursive-reverse [1 2 3 4 5]) (recursive-reverse '(1 2 3 4 5))) 
false 
user=> (= '(1 2 3 4 5) [1 2 3 4 5]) 
true 
user=> (recursive-reverse [1 2 3 4 5]) 
[1 2 3 4 5] 
user=> (recursive-reverse '(1 2 3 4 5)) 
(5 4 3 2 1) 

Answer 1

L'errore Can only recur from tail position significa che non stai chiamando recur come l'ultima espressione nella parte ricorsiva della funzione - infatti, nel codice conj è l'ultima espressione.

Alcuni miglioramenti per rendere il lavoro codice:

• chiedere se la raccolta è vuota come il caso base, invece di confrontare se la sua lunghezza è inferiore a due
• conj riceve una collezioneper la sua primo parametro, non un elemento
• È un'idea migliore usare cons anziché conj (che aggiunge nuovi elementi in luoghi diversi a seconda del tipo di calcestruzzo della raccolta, in base allo documentation).In questo modo, la raccolta restituita verrà annullata se la raccolta di input è una lista o un vettore (sebbene il tipo della raccolta restituita sarà sempre
• un elenco con un singolo elemento (il simbolo coll) e non la raccolta effettiva
• Per invertire correttamente un elenco è necessario scorrere l'elenco di input e aggiungere ciascun elemento all'inizio di un elenco di output; utilizzare un parametro accumulatore per questo
• Per sfruttare la ricorsione in coda, chiamare recur nella posizione di coda della funzione; in questo modo ogni invocazione ricorsiva prende una quantità costante di spazio e lo stack non crescerà senza limiti

Credo che questo sia quello che volevamo ottenere:

(defn recursive-reverse [coll] 
    (loop [coll coll 
     acc (empty coll)] 
     (if (empty? coll) 
      acc 
      (recur (rest coll) (cons (first coll) acc))))) 

Answer 2

È possibile richiamare solo dalla posizione di coda in Clojure. Fa parte del design della lingua ed è una restrizione relativa alla JVM.

È possibile chiamare il nome della funzione (utilizzando la ricorsione) senza ricorrere, e in base alla struttura del programma, ad esempio se si utilizzano sequenze pigri o meno, è possibile che non si verifichi un aumento dello stack. Ma è meglio usare ricorrere, e l'uso di ricorrenza con ricorrenza ti consente alcuni collegamenti locali.

Ecco un esempio da 4Clojure.com dove la ricorsione viene utilizzata senza ricorrere.

(fn flt [coll] 
    (let [l (first coll) r (next coll)] 
    (concat 
     (if (sequential? l) 
     (flt l) 
     [l]) 
     (when (sequential? r) 
     (flt r))))) 

Answer 3

Il modo più semplice per rendere il codice il lavoro è quello di utilizzare il nome della funzione, invece di recur:

(defn recursive-reverse [coll] 
    (loop [coll coll] 
    (if (< (count coll) 2) '(coll) 
     (conj (first coll) (recursive-reverse (rest coll))) 
    ))) 

si farà lo stack di chiamate enorme e errore fuori per i grandi ingressi abbastanza, naturalmente.

Ecco un altro modo di scrivere una versione tail-call-friendly di recursive-reverse:

(defn recursive-reverse [s] 
    (letfn [ 
    (my-reverse [s c] 
     (if (empty? s) 
     c 
     (recur (rest s) (conj c (first s)))))] 
    (my-reverse s '()))) 

Si tira voci fuori la testa della lista di input e li aggiunge alla testa della lista dell'accumulatore.

'Posizione di coda' significa solo che lo recur è l'ultima operazione eseguita dalla funzione prima che ritorni. Questo differisce dalla tua soluzione di "ricorsione naturale" in cui c'è ancora lavoro nella funzione tra la chiamata e il ritorno.