What is an instance of Option Type at parsing time?

Question

About option types, the specification of Minizinc (sec. 6.6.3) says:

Overview. Option types defined using the opt type constructor, define types that may or may not be there. They are similar to Maybe types of Haskell implicity adding a new value <> to the type.

[...]

Initialisation. An opt type variable does not need to be initialised at instance-time. An uninitialised opt type variable is automatically initialised to <>.

I would like to parse and process the following constraint with two opt types:

predicate alternative(var opt int: s0, var int: d0,
                      array[int] of var opt int: s,
                      array[int] of var int: d);

However, I am not sure about what should I expect as values for arguments s0 and s when parsing this constraint.

Can I simply ignore the presence of the opt modifier and assume the constraint signature to be equal to the following one?

predicate alternative(var int: s0, var int: d0,
                      array[int] of var int: s,
                      array[int] of var int: d);

If not, how should I handle it?

Answer 1

In MiniZinc variable option types are handled as variables that might not exist. Within the compiler these variables are transformed these variables are interpreted and rewritten in such a way that the FlatZinc output only contains actual variables. Usually this means that an boolean variable is added for every variable that is true if-and-only-if the variable "exists".

For the library writers, there is the option to rewrite it in such a way that your solver will be able to handle best. In the standard library alternative is defined as:

predicate alternative(var opt int: s0, var int: d0,
                  array[int] of var opt int: s,
                  array[int] of var int: d) =
          assert(index_set(s) = index_set(d),
                 "alternative: index sets of third and fourth argument must be identical",
          sum(i in index_set(s))(bool2int(occurs(s[i]))) <= 1 /\
          span(s0,d0,s,d)
      );

Notice that the occurs intrinsic is used to test if a variable exists. More intrinsics for variable types can be found in the MiniZinc library: http://www.minizinc.org/doc-lib/doc-optiontypes.html. If necessary, you can also use a let-expression to create extra variable and then map the predicate to an solver intrinsic predicate.

Even if there is no better decomposition of the optional type predicate for your solver, it can still be worthwhile to implement the predicate without option types. Because of MiniZinc's overloading, that implementation will be used whenever the predicate is called with arrays of non-option variable types. (Note though that the alternative predicate is specifically meant for "optional tasks" and is unlikely to be called that way).