[Haskell] Re: No fun with phantom types
Michael Marte
marte at pms.informatik.uni-muenchen.de
Mon Oct 27 15:48:28 EDT 2008
Hello David,
thank you, the functional dependency solved the problem! Nevertheless, I think
it is worth considering the phantom type variable a second time. It makes
easy things quite hard and requires a lot of not-(yet?)-standard features of
the type system. As there is usually no second problem instance a variable
could escape to, the price for the theoretical safety is probably too high.
I studied your solver for arithmetic constraints and, after some thinking, I
prefer your approach over mine because it is more natural (no posting
function required that implements the compiler) though it does not allow for
automatic analysis and transformations. For example, with the ADT approach a
system of linear equalities and inequalities could be recognized as a linear
program and replaced by a specialized global lp constraint. However, as the
lp constraint can be applied directly as well, omitting the transformation
stage does not hurt.
Concering bad performance, there are several things that come to my mind:
* Domain access in not O(1). varMap should be replaced by an array.
* Pruning IntSet domains is inefficient: filterLessThan and filterGreaterThan
are O(n) due to the use of IntSet.filter which should be replaced by
IntSet.split.
* No search strategy: One should always try to label one of the "most
constrained" variables. A proven way to do this is to label one of the
variables with the smallest domain.
* Splitting domains instead of labelling: Depending on the problem, on the way
it is modelled, and on the operational properties of the constraints employed
in the model, it may be better to split domains, i.e. choose a non-ground
variable x and generate two subproblems, one with x .=<. a and one with x .>.
a where a is some element between the lower and upper bound of x, usually the
middle.
* Correctness: The implementation of .*. is faulty; its pruning is too strong:
*FD> clp (do x <- newNamedVar (0, 9) "x"; 10 .*. x .==. 90)
_1: (10,10)
_2: (90,90)
_3: (90,90)
x: (9,9) ? ;
no
*FD> clp (do x <- newNamedVar (0, 9) "x"; 10 .*. x .==. 80)
no
(The clp and newNamedVar functions are described on
http://mmartedp.blogspot.com/ and contained in the patch I attached to this
mail.)
That's why sendMoreMoney has no solutions and, of course, bugs like this one
may render easy problems difficult by pruning solutions resulting in long
runtimes.
Michael
On Friday 24 October 2008 01:17:07 am you wrote:
> Hi Michael,
>
> You need a functional depenency in the class to make this work. Something
> like
>
> class MakeAExp a s | a -> s where
> makeAExp :: a -> AExp s
>
> should work, although I haven't tested it with your code.
>
> I did actually extend my FD constraint solver with arithmetic
> constraints myself, but I never got time to post it on my blog. It's
> also very inefficient at the moment, at least compared to the clp(fd)
> solver in GnuProlog.
>
> I took a slightly different approach to you. Instead of using an
> algebraic data type for expressions, I represent each node in the
> expression as a new FDVar in the constraint store.
> I've attached a copy of my code if you're interested. Let me know how
> you get on.
>
> David
-------------- next part --------------
A non-text attachment was scrubbed...
Name: clpStuffPatch.zip
Type: application/x-zip
Size: 1461 bytes
Desc: not available
Url : http://www.haskell.org/pipermail/haskell/attachments/20081027/5c008a11/clpStuffPatch-0001.bin
More information about the Haskell
mailing list