Accumulatori, conj e ricorsione
https://stackoverflow.com//questions/10666228
-
11-12-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho risolto 45 problemi da 4clojure.com e ho notato un problema ricorrente nel modo in cui provo a risolvere alcuni problemi utilizzando la ricorsione e gli accumulatori.
Cercherò di spiegare al meglio che posso quello che sto facendo per finire con soluzioni fugge sperando che alcuni Clojurer "ottengano" ciò che non ottengo.
Ad esempio, il problema 34 chiede di scrivere una funzione (senza utilizzare allineare) prendendo due numeri interi come argomenti e crea un intervallo (senza utilizzare range).In poche parole, fai (...1 7) e ottieni (1 2 3 4 5 6).
Ora, questa domanda non riguarda la risoluzione di questo particolare problema.
E se io Volere risolvere questo problema utilizzando la ricorsione e un accumulatore?
Il mio processo di pensiero è questo:
Devo scrivere una funzione che accetta due argomenti, con cui inizio (fn [x y] )
Avrò bisogno di ricorsione e dovrò tenere traccia di una lista, userò un accumulatore, quindi scrivo una seconda funzione all'interno della prima prendendo un argomento aggiuntivo:
(FN [XY
((fn g [xy acc] ...) x y '())
(a quanto pare non riesco a formattare correttamente il codice Clojure su SO!?)
Qui non sono già sicuro di farlo correttamente:la prima funzione dovere prendi esattamente due argomenti interi (non la mia chiamata) e non ne sono sicuro:se voglio usare un accumulatore, posso usare un accumulatore senza creare una funzione annidata?
Allora voglio farlo cong, ma non posso fare:
(conj 0 1)
quindi faccio cose strane per assicurarmi di avere prima una sequenza e alla fine ottengo questo:
(fn
[x y]
((fn g [x y acc] (if (= x y) y (conj (conj acc (g (inc x) y acc)) x)))
x
y
'()))
Ma poi questo produce questo:
(1 (2 (3 4)))
Invece di questo:
(1 2 3 4)
Quindi finisco per fare un ulteriore appiattire e funziona ma è totalmente brutto.
Comincio a capire alcune cose e comincio anche, in alcuni casi, a "pensare" in modo più clojuresco ma ho qualche problema a scrivere la soluzione.
Ad esempio qui ho deciso:
- utilizzare un accumulatore
- ricorrere per incremento X finché non raggiunge sì
Ma finisco con la mostruosità di cui sopra.
Ci sono quantità di modo per risolvere questo problema e, ancora una volta, non è quello che sto cercando.
Quello che cerco è come, dopo aver deciso di cons/conj, utilizzare un accumulatore e ricorsivare, posso finire con questo (non scritto da me):
#(loop [i %1
acc nil]
(if (<= %2 i)
(reverse acc)
(recur (inc i) (cons i acc))))
Invece di questo:
((fn
f
[x y]
(flatten
((fn
g
[x y acc]
(if (= x y) acc (conj (conj acc (g (inc x) y acc)) x)))
x
y
'())))
1
4)
Immagino che sia un inizio riuscire a risolvere alcuni problemi, ma sono un po' deluso dalle brutte soluzioni che tendo a produrre...
Soluzione
Penso che ci siano un paio di cose da imparare qui.
Prima , una sorta di regola generale - le funzioni ricorsive hanno in genere un ordine naturale e aggiungendo un accumulatore che si inverte. È possibile vedere che, perché quando viene eseguita una funzione ricorsibile "Normale" ( senza Accumulatore), funziona un po 'di lavoro per calcolare un valore, quindi ricorsi a generare la coda dell'elenco, finalmente termina con un elenco vuoto . Al contrario, con un accumulatore, inizi con l'elenco vuoto e aggiungi le cose alla parte anteriore - sta crescendo nell'altra direzione .
Quindi in genere, quando aggiungi un accumulatore, ottieni un ordine invertito.
Ora spesso questo non ha importanza. Ad esempio, se stai generando non una sequenza ma un valore che è l'applicazione ripetuta di un operatore commutativo (come aggiunta o moltiplicazione). Quindi ottieni la stessa risposta in entrambi i modi.
Ma nel tuo caso, importa. Hai intenzione di prendere la lista all'indietro:
.
(defn my-range-0 [lo hi] ; normal recursive solution
(if (= lo hi)
nil
(cons lo (my-range-0 (inc lo) hi))))
(deftest test-my-range-1
(is (= '(0 1 2) (my-range-0 0 3))))
(defn my-range-1 ; with an accumulator
([lo hi] (my-range-1 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (cons lo acc)))))
(deftest test-my-range-1
(is (= '(2 1 0) (my-range-1 0 3)))) ; oops! backwards!
E spesso il meglio che puoi fare per risolvere questo è solo invertire quell'elenco alla fine.
Ma qui c'è un'alternativa - possiamo effettivamente fare il lavoro all'indietro. Invece di incrementazione il limite inferiore che puoi decrementare il limite elevato:
.
(defn my-range-2
([lo hi] (my-range-2 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(let [hi (dec hi)]
(recur lo hi (cons hi acc))))))
(deftest test-my-range-2
(is (= '(0 1 2) (my-range-2 0 3)))) ; back to the original order
[Nota: c'è un altro modo di invertire le cose di seguito; Non ho strutturato molto bene il mio argomento]
Secondo , come puoi vedere in my-range-1 e my-range-2, un bel modo di scrivere una funzione con un accumulatore è come una funzione con due diversi gruppi di argomenti. Questo ti dà un'implementazione molto pulita (IMHO) senza la necessità di funzioni nidificate.
.
Inoltre hai alcune domande generali su sequenze, conj e simili. Qui clojure è tipo disordinato, ma anche utile. Sopra ho dato una visione molto tradizionale con elenchi basati su contro. Ma Clojure ti incoraggia ad usare altre sequenze. E a differenza degli elenchi contro, i vettori crescono a destra, non a sinistra. Quindi un altro modo per invertire quel risultato è usare un vettore:
.
(defn my-range-3 ; this looks like my-range-1
([lo hi] (my-range-3 lo hi []))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (conj acc lo)))))
(deftest test-my-range-3 ; except that it works right!
(is (= [0 1 2] (my-range-3 0 3))))
Qui conj si aggiunge a destra. Non ho usato conj in my-range-1, quindi qui è re-scritto per essere più chiaro:
.
(defn my-range-4 ; my-range-1 written using conj instead of cons
([lo hi] (my-range-4 lo hi nil))
([lo hi acc]
(if (= lo hi)
acc
(recur (inc lo) hi (conj acc lo)))))
(deftest test-my-range-4
(is (= '(2 1 0) (my-range-4 0 3))))
Si noti che questo codice appare molto simile a my-range-3 ma il risultato è all'indietro perché stiamo iniziando con una lista vuota, non un vettore vuoto. In entrambi i casi, conj aggiunge il nuovo elemento nella posizione "naturale". Per un vettore che è a destra, ma per una lista è a sinistra.
E mi è venuto appena visto che potresti non capire davvero cosa sia una lista. Fondamentalmente un cons crea una scatola contenente due cose (i suoi argomenti). Il primo è il contenuto e il secondo è il resto della lista. Quindi la lista (1 2 3) è fondamentalmente (cons 1 (cons 2 (cons 3 nil))). Al contrario, il vettore [1 2 3] funziona più come un array (anche se penso che sia implementato utilizzando un albero).
Così conj è un po 'confuso perché il modo in cui funziona dipende dal primo argomento. Per una lista, chiama cons e quindi aggiunge cose a sinistra. Ma per un vettore si estende la matrice (la cosa) a destra. Inoltre, nota che conj prende una sequenza esistente come prima ARG e cosa da aggiungere come secondo, mentre cons è il contrario (cosa da aggiungere arriva prima).
.
Tutto il codice sopra disponibile su https://github.com/andrewcooke/clojure-labingeleth/a >
.
Aggiornamento: ho riscritto i test in modo che il risultato atteso sia un elenco quotato nei casi in cui il codice genera un elenco. = confronterà elenchi e vettori e restituirà true se il contenuto è lo stesso, ma renderlo esplicito mostra più chiaramente ciò che stai effettivamente ottenere in ogni caso. Nota che '(0 1 2) con un ' davanti è proprio come (list 0 1 2): il ' arresta l'elenco da valutare (senza di esso, 0 verrà considerato come un comando).
Altri suggerimenti
Dopo aver letto tutto ciò, non sono ancora sicuro del motivo per cui hai bisogno di un accumulatore.
((fn r [a b]
(if (<= a b)
(cons a (r (inc a) b))))
2 4)
=> (2 3 4)
Sembra una soluzione ricorsittiva piuttosto intuitiva. L'unica cosa che cambierei nel codice "reale" è usare lazy-seq in modo da non esaurire la pila per grandi intervalli.
Come ho avuto la soluzione:
Quando stai pensando di usare la ricorsione, trovo che aiuta a provare a dichiarare il problema con i termini più possibili che puoi pensare e cercare di distribuire il più "lavoro" alla ricorsione stessa. In particolare, se si sospetta di poter cadere uno o più argomenti / variabili, che di solito è il modo di andare - almeno se vuoi che il codice sia facile da capire e debug; A volte si finisce per compromettere la semplicità a favore della velocità di esecuzione o riducendo l'utilizzo della memoria.
In questo caso, ciò che pensavo quando ho iniziato a scrivere è stato: "Il primo argomento alla funzione è anche l'elemento iniziale della gamma e l'ultimo argomento è l'ultimo elemento". Il pensiero ricorsivo è qualcosa che ti sei in grado di allenarti, ma una soluzione abbastanza ovvia è quindi dire: A Intervallo [a, b] è una sequenza a partire da elemento a seguito da A Intervallo di [a + 1, b]. Quindi le gamme possono effettivamente essere descritte in modo ricorsivo. Il codice che ho scritto è praticamente un'implementazione diretta di quell'idea.
Addendum:
Ho trovato che quando si scrive il codice funzionale, gli accumulatori (e gli indici) sono meglio evitati. Alcuni problemi richiedono loro, ma se riesci a trovare un modo per sbarazzarsi di loro, di solito stai meglio se lo fai.
Addendum 2:
Per quanto riguarda le funzioni ricorsive e le liste / sequenze, il modo più utile per pensare quando scrivi quel tipo di codice è quello di dichiarare il problema in termini di "il primo elemento (testa) di una lista" e "Il resto della lista (coda)".
Non posso aggiungere alle già buone risposte che hai ricevuto, ma risponderò in generale. Mentre attraversi il processo di apprendimento di Clojure, potresti scoprire che molte ma non tutte le soluzioni possono essere risolte usando il clojure incorporato, come la mappa e anche il pensiero di problemi in termini di sequenze. Questo non significa che non dovresti risolvere le cose in modo ricorsivo, ma sentirai - e credo che sia un consiglio saggio - che la ricorsione di Clojure è per risolvere problemi di livello molto basso non è possibile risolvere un altro modo.
Mi capita di fare un sacco di elaborazione dei file .csv e ha recentemente ricevuto un commento che Nth crea dipendenze. Lo fa, e l'uso delle mappe può consentirmi di ottenere elementi per il confronto per nome e non posizione.
Non ho intenzione di buttare fuori il codice che utilizza NTH con i dati analizzati Clojure-CSV in due piccole applicazioni già in produzione. Ma ho intenzione di pensare alle cose in un modo più sequenziale la prossima volta.
È difficile da imparare dai libri che parlano di vettori e nth, loop .. Recupere e così via, e poi realizzare l'apprendimento del clojure ti cresce da lì.
Una delle cose che ho scoperto che è buona per imparare il clojure, la comunità è rispettosa e disponibile. Dopotutto, stanno aiutando qualcuno il cui primo linguaggio di apprendimento è stato Fortran IV su un cyber CDC con le schede di punch e il cui primo linguaggio di programmazione commerciale era PL / I.
Se risolvessi questo problema utilizzando un accumulatore, farei qualcosa del tipo:
user=> (defn my-range [lb up c]
(if (= lb up)
c
(recur (inc lb) up (conj c lb))))
#'user/my-range
quindi chiamalo con
#(my-range % %2 [])
Certo, lo userei letfn o qualcosa da aggirare non avendo defn disponibile.
Quindi sì, hai bisogno di una funzione interna per utilizzare l'approccio dell'accumulatore.
Il mio processo di pensiero è che una volta che avrò finito, la risposta che voglio restituire sarà nell'accumulatore.(Ciò contrasta con la tua soluzione, in cui lavori molto per trovare la condizione finale.) Quindi cerco la mia condizione finale e se l'ho raggiunta, restituisco l'accumulatore.Altrimenti aggiungo l'elemento successivo all'accumulatore e ricorro a un caso più piccolo.Quindi ci sono solo 2 cose da capire, qual è la condizione finale e cosa voglio inserire nell'accumulatore.
Usare un vettore aiuta molto perché conj verrà aggiunto ad esso e non sarà necessario utilizzarlo reverse.
Anch'io sono su 4clojure, comunque.Sono stato occupato e sono rimasto indietro ultimamente.
Sembra che la tua domanda sia di più su "Come imparare" allora un problema tecnico / codice. Si finisce per scrivere quel tipo di codice perché da qualsiasi modo o fonte che hai imparato la programmazione in generale o clojure in specifica ha creato una "autostrada neurale" nel tuo cervello che ti fa pensare alle soluzioni in questo particolare modo e finisci il codice di scrittura come questo. Fondamentalmente ogni volta che affronti qualche problema (in questa particolare caso di ricorsione e / o accumulazione) finisci usando quella "autostrada neurale" e inventa sempre quel tipo di codice.
La soluzione per sbarazzarsi di questa "autostrada neurale" è smettere di scrivere il codice per il momento, tenere quella tastiera e iniziare a leggere un sacco di codice clojure esistente (dalle soluzioni esistenti del problema di 4Clojure per aprire i progetti di GitHub) E pensaci profondamente (anche leggere una funzione 2-3 volte per lasciarla davvero accontentarsi del tuo cervello). In questo modo finiresti per distruggere la tua "autostrada neurale" esistente (che produce il codice che scrivi ora) e creerà una nuova "autostrada neurale" che produrrebbe il codice clojure bello e idiomatico. Inoltre, cerca di non saltare al codice di digitazione non appena hai visto un problema, piuttosto concederti un po 'di tempo per pensare in modo chiaro e profondamente del problema e delle soluzioni.
