Introduzione
Ricorsione in coda
Quando si usa la ricorsione attraverso gli enumerabili (liste, bitstring e stringhe), ci sono spesso due aspetti da considerare:
- quanta memoria serve per conservare la traccia delle chiamate ricorsive
- come costruire la soluzione in modo efficiente
Per affrontare questi aspetti, si può usare un accumulatore.
Un accumulatore è una variabile che viene passata in aggiunta ai dati. Serve a trasmettere lo stato attuale dell'esecuzione della funzione, da una chiamata all'altra, finché non si raggiunge il caso base. Nel caso base, l'accumulatore viene usato per restituire il valore finale della chiamata ricorsiva.
Gli accumulatori dovrebbero essere inizializzati da chi scrive la funzione, non da chi la usa. Per ottenere questo, definisci due funzioni: una funzione pubblica che prende come argomenti solo i dati necessari e inizializza l'accumulatore, e una funzione privata che prende anche un accumulatore. In Elixir, è una pratica comune anteporre do_ al nome della funzione privata.
# Count the length of a list without an accumulator
def count([]), do: 0
def count([_head | tail]), do: 1 + count(tail)
# Count the length of a list with an accumulator
def count(list), do: do_count(list, 0)
defp do_count([], count), do: count
defp do_count([_head | tail], count), do: do_count(tail, count + 1)
L'uso di un accumulatore ci permette di trasformare funzioni ricorsive in funzioni ricorsive in coda. Una funzione è ricorsiva in coda se l'ultima cosa eseguita dalla funzione è una chiamata a se stessa.
Istruzioni
Nel tuo laboratorio di ricerca sul DNA, hai sperimentato vari modi per comprimere i dati delle tue ricerche e risparmiare spazio di archiviazione. Un collega di squadra propone di convertire i dati del DNA in una rappresentazione binaria:
| Acido nucleico |
Codice |
| uno spazio |
0000 |
| A |
0001 |
| C |
0010 |
| G |
0100 |
| T |
1000 |
Ci rifletti un po': potrebbe dimezzare i costi di archiviazione necessari, ma a scapito della leggibilità per gli esseri umani. Decidi di scrivere un modulo per codificare e decodificare i dati, così da valutare il risparmio.
1. Codificare un acido nucleico in un valore binario
Implementa encode_nucleotide/1 in modo che accetti il code point dell'acido nucleico e restituisca il valore intero del codice codificato.
DNA.encode_nucleotide(?A)
# => 1
# (which is equal to 0b0001)
2. Decodificare il valore binario nell'acido nucleico
Implementa decode_nucleotide/1 in modo che accetti il valore intero del codice codificato e restituisca il code point dell'acido nucleico.
DNA.decode_nucleotide(0b0001)
# => 65
# (which is equal to ?A)
3. Codificare una charlist di DNA
Implementa encode/1 in modo che accetti una charlist che rappresenta acidi nucleici e spazi e restituisca un bitstring con i dati codificati.
DNA.encode(~c"AC GT")
# => <<18, 4, 8::size(4)>>
4. Decodificare un bitstring di DNA
Implementa decode/1 in modo che accetti un bitstring che rappresenta acidi nucleici e spazi e restituisca i dati decodificati come charlist.
DNA.decode(<<132, 2, 1::size(4)>>)
# => ~c"TG CA"
Esercizio di apprendimento
