José Romildo Malaquias <[EMAIL PROTECTED]> asked:
| Is there any references to memoization techniques?
:
| So, is it straightforward to implement the memo function in
| Haskell 98 or in Clean?
In my case, the memo function was only needed for the type "Env":
memo :: (Env -> a) -> (Env -> a)
Suppose "Env" is just a Bool, it is straightforward to implement
the memo function:
memo f = \x -> if x then fTrue else fFalse
where
fTrue = f True
fFalse = f False
(Assuming the right sharing behavior, which all major compilers
implement).
This technique is actually quite usable for other types
(such as integers) as well, as suggested by Magnus Carlsson
in an informal talk he gave here at the department. The idea
is to have an infinite (binary) lookup table for infinite types.
I re-implemented his ideas, and the module is downloadable from
http://www.cs.chalmers.se/~koen/Code/Memo.hs
What this module gives you is a Haskell'98 implementation of:
class Memo a where
memo :: (a -> b) -> (a -> b)
And instances (), Bool, Int, Lists, Maybe, Either, Tuples, Double, etc.
(It does not work in HBC though because of an "optimization"
(eta-expansion) which is done for class methods, thus losing
sharing).
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
