给定 SML 中的变量列表，生成所有真值分配的列表？

Question

我正在尝试用 SML 编写一个给定变量列表的函数，它 returns 每个可能的布尔赋值的元组列表。

基本上，我希望代码执行此操作：

fun allAssignments ["p", "q"] = 
  [[("p", True),  ("q", True) ]
   [("p", True),  ("q", False)]
   [("p", False), ("q", True) ]
   [("p", False), ("q", False)]]

然而，我写了这个函数，虽然它对我来说很有意义，但我一直收到 tycon 不匹配错误，我无法纠正它：

fun allAssignments nil = [[]]
  | allAssignments (x::xs) = [(x, true)::allAssignments xs] @ [(x, false)::allAssignments xs]

谁能帮我指明正确的方向？谢谢！

Answer 1

根据您的示例，allAssignments 需要具有类型 string list -> (string * bool) list list（或者可能是 'a list -> ('a * bool) list list 或 ''a list -> (''a * bool) list list，但我会坚持使用 string 为简单起见；两种方式的实现都是相同的）。

因此，allAssignments xs 必须具有类型 (string * bool) list list，并且 (x, true) 必须具有类型 string * bool。但是 (x, true) :: allAssignments xs 是类型不匹配，因为 :: 期望它的第二个参数是一个列表，其元素与第一个参数具有相同的类型，而在您的情况下，第二个参数是一个列表，其元素是lists（第一个参数不是）。

如果我们想象一个不实际检查类型的标准 ML 版本，您的 allAssignments 版本将给出以下结果：

allAssignments []→[[]]
allAssignments ["q"]→[[("q", true), []], [("q", false), []]]
allAssignments ["p", "q"]→[[("p", true), [("q", true), []], [("q", false), []]], [("p", false), [("q", true), []], [("q", false), []]]]

如您所见，它并没有真正解决问题。一个问题是 "q" 的赋值比 "p" 的赋值嵌套在更多层的列表中（因此出现类型错误）。另一个问题是 ("p", true) 和 ("p", false) 每个只出现一次，而 ("q", true) 和 ("q", false) 每个出现两次。

要解决此问题，您需要实际“打开”allAssignments xs 并将 (x, true) 添加到它包含的每个单独列表中，然后 (x, false) 也是如此。

这是一种方法，使用 map:

fun allAssignments nil = [nil]
 |  allAssignments (x::xs) =
      (map (fn assignments => (x, true) :: assignments) (allAssignments xs))
      @ (map (fn assignments => (x, false) :: assignments) (allAssignments xs))

虽然我应该提到这个实现根本不是最优的；计算时间和内存使用量都可以显着减少，特别是如果您不关心返回分配的顺序。

给定 SML 中的变量列表，生成所有真值分配的列表？

Generating a list of all truth assignments given a list of variables in SML?

functional-programming

list

sml

smlnj