[Haskell-cafe] Logic programming using lazy evaluation
Henning Thielemann
lemming at henning-thielemann.de
Tue Feb 27 09:54:41 EST 2007
I suspect that someone has already done this: A Haskell library which
solves a system of simple equations, where it is only necessary to derive
a value from an equation where all but one variables are determined. Say
1+2=x -- add 1 2 x
y*z=20 -- times y z 20
x+y=5 -- add x y 5
should be solved as
x=3
y=2
z=10
Of course, it is easy to do this for a finite number of variables and
equations by assigning integer identifiers to the variables, then scanning
the equations repeatedly until all determinable variables are determined.
However, imagine I have an infinite number of equations and an infinite
number of variables, say
1=x0 -- equal 1 x0
2*x0=x1 -- times 2 x0 x1
2*x1=x2 -- times 2 x1 x2
2*x2=x3 -- times 2 x2 x3
...
Accessing variable values by integer identifiers means that the garbage
collector cannot free values that are no longer needed.
Thus I thought about how to solve the equations by lazy evaluation. Maybe
it is possible to ty the knot this way
let (_,_,x0) = add 1 2 x
(y0,z0,_) = times y z 20
(x1,y1,_) = add x y 5
x = alternatives [x0,x1]
y = alternatives [y0,y1]
z = alternatives [z0]
in (solve x, solve y, solve z)
Independent from the question of how to implement 'alternatives' and
'solve' I wonder if there is a less cumbersome way to do this kind of
logic programming in Haskell.
More information about the Haskell-Cafe
mailing list