[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


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