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".

Answer 2

OK, let's break down your code. Here's your 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 ;
    )

The first thing I'm going to do is rewrite it so a Caml programmer will understand it, without changing any of the computations. Primarily this means using pattern matching instead of hd and tl. This transformation is not trivial; it's important to simplify the list manipulation to make it easier to identify the problem with the code. It also makes it more obvious that this function fails if l2 is empty.

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
    )

Now I think the key to your difficulty is the understanding of the semicolon operator. If I write (e1; e2), the semantics is that e1 is evaluated for side effect (think printf) and then the result of e1 is thrown away. I think what you want instead is for the result of e1 to become the new value of accum for the recursive call. So instead of throwing away e1, we make it a parameter (this is the key step where the computation actually changes):

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

Next step is to observe that we've violated the Don't Repeat Yourself principle, and we can fix that by making the base case where l2 is empty:

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

We then clean up a bit:

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

Finally, the repeated calls to append make the code quadratic. This is a classic problem with accumulating parameters and has a classic solution: accumulate the answer list in reverse order:

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

I've changed the name accum to accum'; the prime is conventional for a list in reverse order. This last version is the only version I have compiled, and I haven't tested any of the code. (I did test the code in my other answer).

I hope this answer is more helpful.