Ocaml noobie Q -- how to use accumulating parameters?

Question

I'm trying to learn Ocaml by working on Problem 18 from Project Euler. I know what I want to do, I just can't figure out how to do it.

I've got three lists:

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

I want to add the numbers list2 to the max adjacent number in list1, IOW I would add 6+2, 7+3, 8+4 and 9+5 to get a list [8;10;12;14]. The list line[] is a dummy variable.

Here's my third try:

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

After running this, I would expect line = [9999;8;10;12;14] but instead line = [9999]. OTOH, fu prints out as [999914].

When I step through the code, the code is executing as I expect, but nothing is changing; the accum in the else block is never modified.

I just don't get this language. Can anyone advise?

Answer 1

Well, I think you haven't grasped the essence of functional programming: instead of calling List.append and throwing the value away, you need to pass that value as the parameter accum to the recursive call.

I would tackle this problem by decoupling the triangle geometry from the arithmetic. The first function takes two lists (rows of the triangle) and produces a new list of triples, each containing and element plus that element's left and right child. Then a simple map produces a list containing the sum of each element with its greater child:

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

If you are working on Euler 18, I advise you to look up "dynamic programming".