Ocaml noobie Q - как использовать накапливающиеся параметры?

Question

Я пытаюсь изучить Ocaml, работая над Задача 18 от Project Euler. Я знаю, что я хочу сделать, я просто не могу понять , как сделать это.

У меня есть три списка:

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

Я хочу добавить номера list2 к максимальному соседнему числу в list1, IOW я бы добавил 6 + 2, 7 + 3, 8 + 4 и 9 + 5, чтобы получить список [8; 10; 12; 14] , Строка списка [] является фиктивной переменной.

Вот моя третья попытка:

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

После этого я бы ожидал строку = [9999; 8; 10; 12; 14], но вместо строки = [9999]. OTOH, fu печатается как [999914].

Когда я перебираю код, код выполняется так, как я ожидаю, но ничего не меняется; Накопитель в блоке else никогда не изменяется.

Я просто не понимаю этот язык. Кто-нибудь может посоветовать?

Answer 1

ОК, давайте разберем ваш код. Вот твой оригинал.

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

Первое, что я собираюсь сделать, это переписать его, чтобы программист Caml понял это, без изменения каких-либо вычислений. В первую очередь это означает использование сопоставления с образцом вместо hd и tl. Это преобразование не тривиально; важно упростить манипулирование списком, чтобы упростить выявление проблемы с кодом. Это также делает более очевидным, что эта функция не работает, если l2 пусто.

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
    )

Теперь я думаю, что ключом к вашему затруднению является понимание оператора точки с запятой. Если я напишу ( e1 ; e2 ), семантика такова, что e1 оценивается для побочного эффекта (думаю printf) и затем результат e1 отбрасывается . Я думаю, что вместо этого вы хотите, чтобы результат e1 стал новым значением accum для рекурсивного вызова. Поэтому вместо отбрасывания e1 мы делаем его параметром (, это ключевой шаг , где вычисление фактически изменяется):

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

Следующим шагом является наблюдение, что мы нарушили принцип «Не повторяйся», и мы можем это исправить, сделав базовый случай, когда l2 пуст:

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

Затем мы немного очистим:

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

Наконец, повторные вызовы append делают код квадратичным. Это классическая проблема с накоплением параметров и имеет классическое решение: накапливать список ответов в обратном порядке:

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

Я изменил имя accum на accum'; штрих является обычным для списка в обратном порядке. Эта последняя версия является единственной версией, которую я скомпилировал, и я не тестировал ни один код. (Я проверял код в моем другом ответе).

Надеюсь, этот ответ более полезен.

Answer 2

Ну, я думаю, что вы не поняли суть функционального программирования: вместо вызова List.append и отбрасывания значения вам нужно передать это значение в качестве параметра accum рекурсивному вызову.

Я бы решил эту проблему, отделив геометрию треугольника от арифметики. Первая функция берет два списка (строки треугольника) и создает новый список троек, каждый из которых содержит и элемент плюс левый и правый дочерний элемент этого элемента. Затем простая карта создает список, содержащий сумму каждого элемента с его большим дочерним элементом:

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

Если вы работаете над Euler 18, я советую вам поискать «динамическое программирование».