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

I'm trying to write a function in SML that given a list of variables, it returns a list of tuples of every possible boolean assignment.

Essentially, I want the code to do this:

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

However, I wrote this function and although it makes sense to me, I keep getting tycon mismatch errors and I can't rectify it:

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

Could anyone help point me in the right direction? Thanks!

CodePudding user response：

Per your example, allAssignments needs to have the type string list -> (string * bool) list list (or potentially 'a list -> ('a * bool) list list or ''a list -> (''a * bool) list list, but I'll just stick with string for simplicity; the implementation is the same either way).

So, allAssignments xs must have the type (string * bool) list list, and (x, true) must have the type string * bool. But then (x, true) :: allAssignments xs is a type mismatch, because :: expects its second argument to be a list whose elements have the same type as its first argument, whereas in your case the second argument is a list whose elements are lists (which the first argument is not).

If we imagine a version of Standard ML that didn't actually check types, your version of allAssignments would give the following results:

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

As you can see, it doesn't really work out. One problem is that the assignments of "q" are nested in more levels of lists than the assignments of "p" (hence the type error). Another problem is that ("p", true) and ("p", false) each appear only once, whereas ("q", true) and ("q", false) each appear twice.

To fix this, you need to actually "open up" allAssignments xs and prepend (x, true) to each of the individual lists that it contains, and then the same for (x, false).

Here's one way, using map:

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

though I should mention that this implementation is not at all optimal; both the computation time and the memory usage can be reduced significantly, especially if you don't care about the order in which the assignments are returned.