# [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