Ocaml noobie Q - 如何使用累积参数？

Question

我正在尝试通过从项目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].列表行[]是一个虚拟变量.

这是我的第三次尝试:

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块中的accum永远不会被修改.

我只是不懂这种语言.任何人都可以建议吗？

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,我建议您查看"动态编程".