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

Хорошо, давайте сломаем Ваш код. Вот Ваш оригинал.

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'; начало является стандартным для списка в обратном порядке. Эта последняя версия является единственной версией, которую я скомпилировал, и я не протестировал ни одного кода. (Я действительно тестировал код в своем другом ответе).

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

Ну, я думаю, что Вы не схватили сущность функционального программирования: вместо вызова 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, я советую Вам искать "динамическое программирование".