Ocaml新手问——如何使用累加参数？

Question

我正在尝试通过解决 Project Euler 的 问题 18 来学习 Ocaml。 我知道我想做什么，只是不知道如何去做。

我有三个列表：

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]。 列表 line[] 是一个虚拟变量。

这是我的第三次尝试：

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

运行此命令后，我期望 line = [9999;8;10;12;14]，但改为 line = [9999]。 OTOH，fu 打印输出为 [999914]。

当我单步执行代码时，代码正在按我的预期执行，但没有任何变化； else 块中的累加值永远不会被修改。

我只是听不懂这种语言。 有人可以建议吗？

Answer 1

好吧，我认为您还没有掌握函数式编程的本质：您需要将该值作为参数accum 传递，而不是调用List.append 并丢弃该值> 到递归调用。

我将通过将三角形几何与算术解耦来解决这个问题。 第一个函数采用两个列表（三角形的行）并生成一个新的三元组列表，每个三元组包含 和 元素以及该元素的左子元素和右子元素。 然后，一个简单的映射会生成一个列表，其中包含每个元素及其较大子元素的总和：

(* 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，我建议您查找“动态规划”。

Answer 2

好的，让我们分解你的代码。 这是你的原件。

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 被评估副作用（想想< code>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'； 素数对于逆序列表来说是常规的。 最后一个版本是我编译的唯一版本，我还没有测试任何代码。 （我确实在其他答案中测试了代码）。

我希望这个答案更有帮助。