SML中如何编写给定变量列表生成所有真值赋值的函数

问题原因 #

你当前代码的类型不匹配核心问题出在递归拼接的逻辑上：

• 递归调用allAssignments xs返回的是(string * bool) list list类型，也就是所有子变量的赋值列表的集合
• 你直接写(x, true)::allAssignments xs是试图将单个元组(x, true)插入到「列表的列表」的头部，这不符合cons操作::的类型要求：::要求左侧元素类型和右侧列表的元素类型完全一致，这里左侧是元组，右侧列表的元素是列表，自然类型不匹配。

修复方案 #

你需要对allAssignments xs返回的每一个子赋值列表，分别插入当前变量的true和false取值，再把两部分结果合并，修复后的代码如下：

fun allAssignments nil = [[]]
  | allAssignments (x::xs) = 
      let
        val subAssigns = allAssignments xs
        val trueAssigns = map (fn assign => (x, true) :: assign) subAssigns
        val falseAssigns = map (fn assign => (x, false) :: assign) subAssigns
      in
        trueAssigns @ falseAssigns
      end

效果验证 #

调用allAssignments ["p", "q"]会直接返回你预期的结果：

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

内容的提问来源于stack exchange，提问作者Ness Earthbound