[Caml] Conversione binario decimale

[oleg.fresi]

Salve a tutti. Sto studiando il linguaggio funzionale caml, in particolare sto cercando di risolvere questo esercizio: data una lista di interi contenente solo 0 e 1 che rappresentano un numero binario, convertire questo nel corrispondente in base 10. Ho pensato di ragionare così: prendo la lista, la inverto e man mano sommo tutti i valori moltiplicati per potenze di 2 crescenti, il problema è che non so come esprimerlo col codice, in particlare non so proprio come poter salvare la lista invertita e l'elevamento a potenza. Ho scritto questo codice, che naturalmente non funziona:

let rec rev l = match l with
    [] -> [] 
  | h::t -> rev t @ [h];;

let rec f l = match l with
    [] -> 0
  | h::t -> let k = rev l in match k with
      [] -> 0
    | k::v -> k * 2 + f v;;

Sapreste aiutarmi a risolvere questo problema?

[probid]

Non è necessario rovesciare la lista, pensa a come funziona la ricorsione.

Per l'elevamento a potenza o utilizzi una funzione ausiliaria con un parametro che rappresenta l'indice del passo corrente oppure puoi osservare che l'esponente corrisponde ad ogni passo alla lunghezza della coda.

Forse può esserti utile anche considerare che moltiplicare per $2^i$ equivale a shiftare a sinistra di $i$ posizioni.

[apatriarca]

Non serve calcolare le potenze di \(2\) esplicitamente né rovesciare la lista. Sia \(P\) il valore della lista binaria corrispondente alle prime \(i\) cifre. Abbiamo ovviamente che \(P[0] = 0\). Inoltre \(P[N]\) (dove \(N\) è la lunghezza della tua lista) è il risultato che vuoi ottenere. Sia quindi che la \(i\)-esima cifra è uguale a \(c\), il valore di \(P\) è quindi facilmente calcolabile a partire da \(P[i-1]\). Ti viene in mente un modo per farlo? Supponi di aver letto \(101_b = 5_d\) e di trovare un \(1\). Devi calcolare il risultato \(1011_b = 11\) a partire dai risultati parziali \(5\) e \(1\). Come fai?

Una volta che trovi la risposta non dovrebbe essere difficile convertire il tutto nel codice.

Avrai bisogno di una funzione di supporto che memorizza il valore di \(P[i-1]\).

Un piccolo consiglio è comunque quello di provare ad usare dei nomi un po' più lunghi di [tt]f[/tt]. Va forse bene per delle funzioni di supporto o locali alla tua funzione, ma in generale è più chiaro utilizzare nomi più descrittivi della funzione. In questo caso qualcosa come [tt]bin2dec[/tt] per esempio.

[apatriarca]

Una piccola nota aggiuntiva sul tuo codice. Forse non ti hanno parlato di funzioni tail recursive, ma sono molto importanti per le performance nei linguaggi funzionali. Non conosco bene Caml, ma di solito nei linguaggi funzionali la inversione di una lista va scritta nel seguente modo:

let reverse lst = reverseAcc [] lst

let rec reverseAcc acc lst =
   match lst with
   | [] -> acc
   | h::t = reverseAcc (h @ acc) t

Questo schema è molto comune in codici scritti con linguaggi funzionali perché mentre la tua soluzione utilizza \(O(N)\) spazio, quella che ho scritto viene convertita in un ciclo che ne usa solo una quantità costante.

Generare una lista di potenze di \(2\) non è difficile. Qualcosa del genere dovrebbe funzionare per esempio:

let twoPowers n = 
   let rec twoPowersHelper s n = if n > 0 then (s @ twoPowersHelper (2 * s) (n - 1)) else [] in
   twoPowersHelper 1 n 

Tuttavia nel tuo caso è scomodo usare qualcosa del genere per due ragioni:
1. La funzione richiede il calcolo della lunghezza della tua listae quindi un ulteriore passaggio lungo di essa.
2. Se inizi a includere la lista in questo codice e passi alla versione tail recursive tornerai all'approccio decisamente migliore suggerito nel mio precedente post.

[oleg.fresi]

Grazie mille a tutti per l'intervento, sono riuscito a scrivere il codice in maniera molto semplice!