OCaml：处理列表元素和 int 之间奇偶校验的递归函数

Question

这个函数应该接受两个参数：一个列表和一个整数。如果列表中的一个元素和数字“a”奇偶校验相等，那么它们必须相加，否则这两个数字应该相减。

计算应按以下顺序进行：

• 一开始，残差值r就是a的值，
• lst 的每个元素 e（按列表给出的顺序选取）都会影响残差值：如果 e 和 r 具有相同的奇偶性（均为奇数或均为偶数），则新的 r' 等于 r + 之和e，如果不是那么它应该等于 r - e 的减法，
• 最后的r是期望的结果。

举个例子：

par [4;7;3;6] 5
should return -1, it would work as follows :
5 and 4 have a different parity so we subtract -> 5 - 4 = 1
1 and 7 are both odd, so we add them together -> 1 + 7 = 8
8 and 3 have a different parity -> 8 - 3 = 5
Finally, 5 and 6 have different parity -> 5 - 6 = -1

我想到了下面这样的事情：

let rec par lst a = 
match lst with 
| [] -> 0
| h::t -> if (h mod 2 == 0 && a mod 2 == 0) || (h mod 2 == 1 && a mod 2 == 1) then a + h
| h::t -> if (h mod 2 == 0 && a mod 2 == 1) || (h mod 2 == 1 && a mod 2 == 0) then a - h :: par t a ;;

编辑1：这是我从编译器得到的错误：

第 4 行，字符 83-88：错误：此表达式的类型为 int，但 表达式应为 unit 类型，因为它是 a 的结果 有条件且无 else 分支

我们的想法是仅使用以下预定义函数 List.hd、List.tl 和 List.length 来构建此函数。

我的上述提议中有什么令人不安的地方以及如何补救？任何人都可以帮我解决这个问题吗？

编辑2： 我能够使用 if...then...else 语法（不是我所知道的 OCaml 最好的语法）来完成所需的操作，但我个人有时在理解模式匹配时遇到更多困难。无论如何，这就是我得到的：

let rec par lst a =  (* Sorry it might hurt some sensible eyes *)  
  if List.length lst = 0 then a
  else
    let r = if (List.hd lst + a) mod 2 == 0 then (a + (List.hd lst))
      else (a - (List.hd lst)) in
    par (List.tl lst) r ;;
val par : int list -> int -> int = <fun>

欢迎提出建议并帮助将其放入模式匹配语法中。

Answer 1

您的代码无法编译。你尝试编译它吗？您是否阅读了编译器产生的错误和警告？您可以将它们添加到您的问题中吗？

关于您的代码的一些评论：

• | h::t -> if ... then ...

  应该是

  | h::t when ... -> ...

  ;

• (h mod 2 == 0 && a mod 2 == 0) || (h mod 2 == 1 && a mod 2 == 1)

  可以简化为

  (h - a) mod 2 == 0

  ;
• 编译器希望知道匹配是详尽的；特别是，您不需要在匹配的第三行中重复测试（只有在第二行测试为 false 时才会读取第三行）；
• 你错过了匹配第二行的递归调用；
• 在匹配的第三行中，您返回一个列表而不是数字（编译器应该明确告诉您类型不匹配！您没有阅读编译器错误消息吗？）；
• 在匹配的第一行，如果列表为空，则返回 0。当到达列表末尾时，您确定 0 是您要返回的值吗？那你计算出来的残值呢？
• 一旦您将此版本的代码修复为递归函数，我建议尝试使用

  List.fold_left

  编写解决相同问题的代码，而不是像您建议的那样使用

  List.hd

  和

  List.tl

  。

当我第一次写我的答案时，我包含了你的代码的固定版本，但我认为我通过分发解决方案而不是让你弄清楚它会对你造成伤害。

Answer 2

这是折叠的自然情况，但您不能使用

List.fold_left

，所以让我们使用您可以使用的函数重新实现它。

# let rec fold_left f i lst =
    if lst = [] then i
    else
      let x = List.hd lst in
      let xs = List.tl lst in
      fold_left f (f i x) xs;;
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

如果我们使用模式匹配，这会更加简单。

let rec fold_left f i = 
  function
  | [] -> i 
  | x::xs -> fold_left f (f i x) xs

现在我们只需要一个函数在折叠的每次迭代上运行。

# let even x = x mod 2 == 0 in
  let odd x = not @@ even x in
  let parity a b = (even a && even b) || (odd a && odd b) in
  fold_left 
    (fun a b -> 
       if parity a b then a + b 
       else a - b) 
    5 
    [4; 7; 3; 6];;
- : int = -1

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  5 
  [4; 7; 3; 6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  1 
  [7; 3; 6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  8 
  [3; 6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  5 
  [6]

fold_left 
  (fun a b -> 
     if parity a b then a + b 
     else a - b) 
  (-1) 
  []

-1