Is there any references to memoization techniques? I could not find
any reference to memoization facilities in the Haskell report and
library report. Neither in the Clean report. After looking at GHC,
Hugs98 and nhc98, I have found that GCH provides the memo function
used in the example. Looking at it, it does not look easily portable.
So, is it straightforward to implement the memo function in
Haskell 98 or in Clean?
Romildo
==========================================================================
On Thu, Dec 02, 1999 at 12:08:58PM +0100, Koen Claessen wrote:
> 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
>
--
Prof. José Romildo Malaquias <[EMAIL PROTECTED]>
Departamento de Computação
Universidade Federal de Ouro Preto
Brasil
