Michael Erik Florentin Nielsen <[EMAIL PROTECTED]> writes:
| There are no problems in having infix operators with more than two
| parameters, eg. the operators `plus` and `times` below both take a third
| parameter: [...]
The problem is that you lose sharing. If you define:
newtype N a
= N (Env -> a)
plus :: N Int -> N Int -> N Int
plus (N f) (N g) = N (\env -> f env + g env)
(Your numbers would just be N Int, with Env = Int). And then later,
you say:
let x :: N Int
x = veryBigExpression
in plus x x
Then "veryBigExpression" depending on an "Env" gets computed twice if you
finally provide the "Env".
One solution is to define "N" to be a monad, in order to be explicit about
sharing.
do x <- veryBigExpression
... x ... x ... -- no problem here
This clutters up the expressions a lot, so it is no acceptable
solution.
Another solution, which works in this case, is to memoize the function in
an N. So instead of using the constructor N directly, you use "memoN":
memoN :: (Env -> a) -> N a
memoN f = N (memo f)
If you redefine all operations as follows:
plus :: N Int -> N Int -> N Int
plus (N f) (N g) = memoN (\env -> f env + g env)
Then the problem is gone.
I used this trick recently to create a Haskell binding to a theorem prover
that required an extra argument (the theorem prover object) to every
"binary" operator. It works well in practise.
One possible problem though is that you lose equality on types like "N a".
If you really want equality *and* sharing, (but care a little bit less
about some particular laws that Haskell "has" -- which are by the way not
defined anywhere anyway) you might want to take a look at the following
paper:
"Observable Sharing for Functional Circuit Description",
Koen Claessen, David Sands, ASIAN '99.
Available from: http://www.cs.chalmers.se/~koen/publications.html
Regards,
Koen.
--
Koen Claessen http://www.cs.chalmers.se/~koen
phone:+46-31-772 5424 e-mail:[EMAIL PROTECTED]
-----------------------------------------------------
Chalmers University of Technology, Gothenburg, Sweden
