[Haskell] Re: No fun with phantom types

[Michael Marte]

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