使用 fold 检查列表是否可以被 int 和 return bool list ocaml 整除

Question

我正在尝试实现一个接受 int 和数字列表的函数，并检查列表中的所有元素是否 div 是 int 可用的，因为 example:div_by_x 2 [ 1;3;4;8;0] = [假;假;真;真;真] 我有一个辅助函数，它在可行时只是 returns true 或 false：

let divisible x i = 
     if i mod x = 0 then true else false;;

有了这个，我已经实现了一个有效的递归 div 函数，它是：

let rec div_by_x x y = match y with 
    [] -> [] 
   | (hd :: tl) -> 
      let l1 = div_by_x x tl in divisible x hd :: l1;;

但现在我正在尝试使用 fold 函数实现 div_by_x，定义为：

let rec fold f a l = match l with
   [] -> a
   | (h::t) -> fold f (f a h) t
;;

我对如何在保持正在进行的列表的同时列出列表感到困惑。到目前为止我有

let div_by_x x y= fold divisible x y [] y;;

这似乎不起作用，并且对我大喊大叫：“

Error: This expression has type int -> int -> bool but an expression was expected of type ('a -> 'b -> 'c) -> 'd -> 'a -> 'b -> 'c Type int is not compatible with type 'a -> 'b -> 'c "

有什么帮助吗？谢谢！

Answer 1

您想折叠一个执行一个增量计算步骤的函数。对于您的问题，一个增量步骤包括确定整除性并将生成的布尔值添加到列表中。您正在尝试折叠仅确定可除性的函数。

我认为，首先要做的是弄清楚折叠函数的实际外观。如果查看折叠的类型，您可以看到所需函数的类型：

# let rec fold f a l = match l with
   | [] -> a
   | (h::t) -> fold f (f a h) t ;;
val fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a = <fun>

折叠函数应该（通常）具有类型 'a -> 'b -> 'a。换句话说，它采用到目前为止的累积答案和输入列表的下一个元素，然后 returns 一个新的累积答案。

对于您的问题，具体类型将是 bool list -> int -> bool list。

您的函数 divisible 的类型为 int -> int -> bool，与您的需要不太接近。

当您弄清楚函数应该是什么样子时，调用可能如下所示：

let div_by_x x y =
    let myfun a b = <<test b for divisibility by x, add to a>> in
    fold myfun [] y

如果您想了解柯里化函数（值得了解），您的定义可能如下所示：

let myfun x a b = . . .

let div_by_x x y = fold (myfun x) [] y

（由于您的折叠是左折叠，您可能会发现它以相反的顺序生成列表。）

使用 fold 检查列表是否可以被 int 和 return bool list ocaml 整除

Using fold to check if a list is divisible by an int and return bool list ocaml

int

ocaml

boolean

fold