Ocaml noobie Q - come utilizzare i parametri di accumulo?

Question

Sto cercando di imparare Ocaml lavorando su Problem 18 da Project Euler. So cosa voglio fare, non riesco a capire come per farlo.

Ho tre liste:

let list1 = [1;2;3;4;5];; 
let list2 = [ 6;7;8;9];; 
let line = [9999];; 

voglio aggiungere i numeri lista2 al numero adiacente massimo in lista1, IOW vorrei aggiungere 6 + 2, 7 + 3, 8 + 4 e 9 +5 per ottenere una lista [8; 10; 12; 14]. La riga di lista [] è una variabile fittizia.

Ecco il mio terzo tentativo:

let rec meld3 l1 l2 accum = 
    if List.length l2 = 1 then 
    List.append accum [ (hd l2 + max (hd l1) (hd (tl l1)))] 
else 
    (
    List.append accum [ (hd l2 + max (hd l1) (hd (tl l1)))]; 
    meld3 (tl l1) (tl l2) accum ; 
    ) 
;; 

let fu = meld3 list1 list2 line ;; 

List.iter print_int fu;; 

Dopo l'esecuzione di questo, mi sarei aspettato linea = [9999; 8; 10; 12; 14], ma invece la linea = [9999]. OTOH, fu stampato come [999914].

Quando passo il codice, il codice è in esecuzione come previsto, ma non sta cambiando nulla; l'accumulo nel blocco else non viene mai modificato.

Non capisco questa lingua. Qualcuno può consigliare?

Answer 1

Beh, penso che non hai afferrato l'essenza della programmazione funzionale: invece di chiamare List.append e gettando via il valore, è necessario passare tale valore come parametro accum alla chiamata ricorsiva.

Vorrei affrontare questo problema disaccoppiando la geometria del triangolo dall'aritmetica. La prima funzione prende due liste (righe del triangolo) e produce una nuova lista di triple, ciascuna contenente ed elemento più il figlio sinistro e destro di quell'elemento. Poi una semplice mappa produce un elenco contenente la somma di ogni elemento con la sua maggiore bambino:

(* function to merge a list l of length N with a list l' of length N+1, 
    such that each element of the merged lists consists of a triple 
    (l[i], l'[i], l'[i+1]) 
*) 

let rec merge_rows l l' = match l, l' with 
    | [], [last] -> [] (* correct end of list *) 
    | x::xs, y1::y2::ys -> (x, y1, y2) :: merge_rows xs (y2::ys) 
    | _ -> raise (Failure "bad length in merge_rows") 

let sum_max (cur, left, right) = cur + max left right 

let merge_and_sum l l' = List.map sum_max (merge_rows l l') 

let list1 = [1;2;3;4;5] 
let list2 = [ 6;7;8;9] 

let answer = merge_and_sum list2 list1 

Se si sta lavorando su Euler 18, vi consiglio di guardare in alto "programmazione dinamica".

Answer 2

OK, analizziamo il codice. Ecco il tuo originale.

let rec meld3 l1 l2 accum = 
    if List.length l2 = 1 then 
    List.append accum [ (hd l2 + max (hd l1) (hd (tl l1)))] 
else 
    (
    List.append accum [ (hd l2 + max (hd l1) (hd (tl l1)))]; 
    meld3 (tl l1) (tl l2) accum ; 
    ) 

La prima cosa che ho intenzione di fare è riscrivere così un programmatore Caml lo capirà, senza cambiare nessuno dei calcoli. In primo luogo ciò significa utilizzare la corrispondenza del modello anziché hd e tl. Questa trasformazione è non banale; è importante semplificare la manipolazione delle liste per semplificare l'identificazione del problema con il codice. Rende anche più ovvio che questa funzione non riesce se l2 è vuoto.

let rec meld3 l1 l2 accum = match l1, l2 with 
| x1::x2::xs, [y] -> (* here the length of l2 is exactly 1 *) 
    List.append accum [ y + max x1 x2 ] 
| x1::x2::xs, y::ys -> (* here the length of l2 is at least 1 *)  
    (List.append accum [ y + max x1 x2 ] 
    ; meld3 (x2::xs) ys accum 
    ) 

Ora penso che la chiave della tua difficoltà sia la comprensione dell'operatore del punto e virgola. Se scrivo (e1; e2), la semantica è che e1 viene valutata per effetto collaterale (si pensi printf) e poi il risultato di e1 viene gettato via. Penso che quello che vuoi invece sia per il risultato di e1 diventi il ​​nuovo valore di accum per la chiamata ricorsiva.Così, invece di buttare via e1, facciamo un parametro (questo è il passo chiave in cui il calcolo cambia in realtà):

let rec meld3 l1 l2 accum = match l1, l2 with 
| x1::x2::xs, [y] -> (* here the length of l2 is exactly 1 *) 
    List.append accum [ y + max x1 x2 ] 
| x1::x2::xs, y::ys -> (* here the length of l2 is at least 1 *)  
    ( 
     meld3 (x2::xs) ys (List.append accum [ y + max x1 x2 ]) 
    ) 

passo successivo è quello di osservare che abbiamo violato la Non ripetere Yourself linea di principio, e siamo in grado di risolvere che facendo il caso base dove l2 è vuota:

let rec meld3 l1 l2 accum = match l1, l2 with 
| x1::x2::xs, [] -> (* here the length of l2 is 0 *) 
    accum 
| x1::x2::xs, y::ys -> (* here the length of l2 is at least 1 *)  
    ( 
     meld3 (x2::xs) ys (List.append accum [ y + max x1 x2 ]) 
    ) 

abbiamo poi ripulire un po ':

let rec meld3 l1 l2 accum = match l1, l2 with 
| _, [] -> accum 
| x1::x2::xs, y::ys -> meld3 (x2::xs) ys (List.append accum [ y + max x1 x2 ]) 

Infine, le chiamate ripetute a append rendono il codice quadratico. Questo è un classico problema con i parametri accumulando e ha una soluzione classica: accumulare la lista risposta in ordine inverso:

let rec meld3 l1 l2 accum' = match l1, l2 with 
| _, [] -> List.rev accum' 
| x1::x2::xs, y::ys -> meld3 (x2::xs) ys (y + max x1 x2 :: accum') 

ho cambiato il nome accum-accum'; il primo è convenzionale per un elenco in ordine inverso. Quest'ultima versione è l'unica versione che ho compilato e non ho testato alcun codice. (Ho provato il codice nella mia altra risposta).

Spero che questa risposta sia più utile.