Ocaml noobie Q - cómo utilizar los parámetros de acumulación?

Question

Estoy tratando de aprender Ocaml trabajando en Problem 18 desde Project Euler. Sé lo que quiero hacer, simplemente no puedo entender cómo para hacerlo.

Tengo tres listas:

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

Quiero añadir los números lista2 al número máximo adyacente en lista1, OIA yo añadiría 6 + 2, 7 + 3, 8 + 4 y 9 +5 para obtener una lista [8; 10; 12; 14]. La línea de la lista [] es una variable ficticia.

Aquí es mi tercer intento:

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;; 

Después de ejecutar esto, yo esperaría línea = [9999; 8; 10; 12; 14] pero en vez de línea = [9999]. OTOH, fu imprime como [999914].

Cuando paso por el código, el código se está ejecutando como esperaba, pero nada está cambiando; la acumulación en el bloque else nunca se modifica.

Simplemente no obtengo este idioma. ¿Alguien puede aconsejar?

Answer 1

Bueno, creo que no ha captado la esencia de la programación funcional: en lugar de llamar al List.append y tirar el valor, debe pasar ese valor como el parámetro accum a la llamada recursiva.

Me gustaría abordar este problema desacoplando la geometría del triángulo de la aritmética. La primera función toma dos listas (filas del triángulo) y produce una nueva lista de tripletas, cada una conteniendo y elemento más el elemento secundario izquierdo y derecho de ese elemento. A continuación, un mapa sencillo produce una lista que contiene la suma de cada elemento con su hijo mayor:

(* 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 

Si usted está trabajando en Euler 18, yo le aconsejo que busque a "programación dinámica".

Answer 2

Bien, desglosemos su código. Aquí está tu original.

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 primera cosa que voy a hacer es volver a escribir por lo que un programador Caml lo entenderá, sin cambiar ninguno de los cálculos. Principalmente, esto significa el uso de patrones en lugar de hd y tl. Esta transformación es no trivial; es importante simplificar la manipulación de la lista para que sea más fácil identificar el problema con el código. También hace que sea más obvio que esta función falla si l2 está vacío.

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 
    ) 

Ahora creo que la clave de su dificultad es la comprensión del operador de punto y coma. Si escribo ( E1; E2 ), la semántica es que e1 se evalúa de efecto secundario (piensa printf) y luego el resultado de E1 se tira. Creo que lo que quiere en su lugar es que el resultado de e1 se convierta en el nuevo valor de accum para la llamada recursiva.Así que en vez de tirar e1, hacemos un parámetro (este es el paso clave, donde el cálculo cambia en realidad):

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 ]) 
    ) 

siguiente paso es observar que hemos violado el no hacer Repita usted mismo principio, y podemos arreglar eso por lo que el caso base, donde l2 está vacía:

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 ]) 
    ) 

a continuación, limpiar un poco:

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 ]) 

Finalmente, las llamadas repetidas a append hacen que el código sea cuadrático. Este es un problema clásico con los parámetros que se acumulan y tiene una solución clásica: acumular la lista de respuestas en el orden 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') 

he cambiado el nombre accum-accum'; el primo es convencional para una lista en orden inverso. Esta última versión es la única versión que he compilado, y no he probado ninguno de los códigos. (Probé el código en mi otra respuesta).

Espero que esta respuesta sea más útil.