1

I have a char list in OCAML. I would like to create a ( (char * bool) list) list of every combination of the chars with true and false.

What I have guess I have to do is something like a List.fold_left, but I am not quite sure how to pull it off.

This is the outline that I tried (OCAML syntax, but not run-able):

let rec var_perm var_list options = 
    match var_list with
        | [] -> options
        | x :: v' ->
            ((x, true) :: (var_perm_intern v')) :: ((x, false) :: (var_perm_intern v'))
;;

let all_options = var_perm ['a';'b'] [];;

should return

[
    [('a',true);('b',true)];
    [('a',true);('b',false)];
    [('a',false);('b',true)];
    [('a',false);('b'false)];
]

Edit: Another example:

let all_options = var_perm ['u';'w';'y'] [];;

should return (order is not important)

[
    [('u',false);('w',false);('y',false)];
    [('u',false);('w',false);('y',true )];
    [('u',false);('w',true );('y',false)];
    [('u',false);('w',true );('y',true )];
    [('u',true );('w',false);('y',false)];
    [('u',true );('w',false);('y',true )];
    [('u',true );('w',true );('y',false)];
    [('u',true );('w',true );('y',true )];
]
yakatz
  • 2,142
  • 1
  • 18
  • 47
  • http://stackoverflow.com/questions/10893521/how-to-take-product-of-two-list-in-ocaml – Gene T Feb 07 '13 at 05:00
  • @GeneT Not the same as what I am looking for. That returns a single list containing all the options. I need a list of lists (as you can see in the question). – yakatz Feb 07 '13 at 06:00

1 Answers1

2

You're close to a correct solution. Specifically:

  • you must remove the _intern suffix in your recursive call
  • the "options" parameter is useless (look at how you do your recursive call, passing only one parameter v'), so you must find out what to return in the [] case
  • the concatenation of "the results of v', plus true for the head var" and " the results of v', plus false for the head var" should be written foo @ bar rather than foo :: bar, because those are two lists you're concatenating, not one element added to a list.
gasche
  • 31,259
  • 3
  • 78
  • 100
  • I was using the `options` as an accumulator. I know that they don't match, but I was not sure if I really needed it. I will try a bit more. – yakatz Feb 06 '13 at 23:43
  • "I need an accumulator" is often a good way to, out of habit, not look at the problem in the face and derive a solution from this specification. What is the set of options for an empty list? Given a set of options for `li`, what set of options should be returned for `var :: li`? There, your function. – gasche Feb 06 '13 at 23:51
  • Your third suggestion about `foo @ bar` does not produce a list of lists like I am looking for. Thoughts? – yakatz Feb 06 '13 at 23:54
  • Thought: you somehow got my (admittedly vague) suggestion in a different way than I intended. I described the three steps that lead me to a working function from your code, so I know it works. I'm just saying that `(@)` has type `'a list -> 'a list -> 'a list`, and that's what you need to use somewhere. – gasche Feb 06 '13 at 23:56