[Haskell-cafe] Negable constraints on boolean normal forms

Yitzchak Gale gale at sefer.org
Thu Jan 1 15:06:13 UTC 2015

I've been using Oleg Genrus' wonderful boolean-normal-forms
library lately, and enjoying it. However, I'm running into
some trouble with overly constrained conversions.

In theory, it's possible to convert between any of the
normal forms without requiring a Negable instance on
the value type. But the conversion mechanism in the
library routes everything via the Boolean type class,
and that ends up slapping a Negable constraint on everything.

You can work around that by embedding your value type
in the free Negable, conveniently provided by the library.
But in practice that causes a lot of trouble. You end
up being required to deal with Neg cases in your result type
that are actually impossible to occur and make no sense
in context. You have to throw bottoms into provably total
functions, or write code that produces meaningless results
that you promise in human-readable comments will never
happen in practice. You also make the code less efficient
by requiring extra passes over the data to "verify" that Neg
isn't there. It's similar to what happens when you try to use
a Monoid where a Semigroup is really needed by bolting on
an artificial "empty" constructor.

One thing you can do to begin with is to remove the
Negable constraints on the NormalForm instances;
I don't see that constraint ever being used. But that still
doesn't solve the main issue.

Perhaps one approach would be to define a
Boolean "bi-monoid" class, where a Boolean bi-monoid
is a like Boolean algebra except without negation.
All of the normal forms are instances of Boolean bi-monoid
even without a Negable constraint on the value type.

If you then relax the constraints on the methods of
CoBoolean and CoBoolean1 to Boolean bi-monoid instead
of Boolean, all of the existing conversion implementations
work without modification and without requiring the Negable

I'm not sure if that creates other problems for some other
use cases of this library though.

Any thoughts?


More information about the Haskell-Cafe mailing list