list - Ocaml 将 bool 列表评估为单个 bool 值

Question

当我试图编写一个解决玩具 SAT 问题的简单程序时，我遇到了以下我无法理解的问题。

我有一个类型变量，定义如下:

type prefix =
     | Not
     | None

type variable = 
     | Fixed of (prefix * bool)
     | Free of (prefix * string)

我可以从中构建变量列表类型的子句和子句列表类型的公式。本质上这归结为有一个公式CNF 或 DNF(这与问题关系不大)。现在尝试简化一个子句时，我会执行以下操作:

• 过滤掉给出列表的子句中的所有固定变量
• 简化变量 (Fixed(Not, true) => Fixed(None, false))

现在我有一个只包含 Fixed 变量的列表，我现在想通过做这样的事情将其组合成一个 Fixed 值

let combine l =
    match l with
    | [] -> []
    | [x] -> [x]
    | (* Get the first two variables, OR/AND them 
         and recurse on the rest of the list *)

我如何用函数式语言实现我想要的行为？我在 OCaml 方面的经验并不多，我还是个初学者。我尝试做 x::xs::rest -> x <||> xs <||> combine rest 但这不起作用。其中 <||> 只是对变量进行或运算的自定义运算符。

感谢您的帮助。

Answer 1

如何使用现有的整洁的高阶函数？

let combine = function
  | x::xs -> List.fold_left (<||>) x xs
  | [] -> failwith "darn, what do I do if the list is empty?"

为了澄清:

List.fold_left : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a

采用获取运行聚合和列表的下一个元素的函数；它返回新聚合；然后我们需要一个初始值和要折叠的项目列表。中缀运算符的使用 <||>括号中的使其成为前缀函数，因此我们可以将其提供给 List.fold_left就像那样——而不是写 (fun a b -> a <||> b) .

如果您的 <||> 中有中性元素运算符，我们称它为one ，我们可以写得更简洁:

let combine = List.fold_left (<||>) one

作为List.fold_left需要三个参数，我们只给了它两个，combine这是variable list -> variable的函数作为前一个。如果您想知道为什么这样做，请查看currying 的概念。