On Nov 7, 2011 7:07 AM, "wren ng thornton" <wren@freegeek.org> wrote:

On 11/6/11 10:51 AM, Bin Jin wrote:

Yes, but I think it's not a funtion since the function didn't use the
parameter. So maybe there is a way to make memorizing possible.

In general, if the argument is not used then

   \x -> E

is equal to

   let e = E in \x -> e

Which we can make strict by adding a bang-pattern or a seq

   let !e = E in \x -> e
 ==
   let e = E in e `seq` \x -> e

The strictness isn't always necessary, but it helps to ensure that GHC doesn't get rid of the let-binding which would take us back to the original (\x -> E). Now, if we use this as the definition of the function, it'll ensure that the computation of E is done as a CAF and hence is memoized (since laziness is call-by-name + memoization).


This trick can be generalized to any function of which parts of it are constant in some subset of parameters. That is, if we have

   \x y z -> E (F (G H x) y) z

then this can be converted into

   let !h = H in
   \x ->
   let !g = G h x in
   \y ->
   let !f = F g y in
   \z ->
   E f z

Now, whenever we want to use this function we pass in as many arguments as we are holding fixed, and force the resulting function in order to memoize the initial computations. For example, if the above function is called foo, then we could use it like:

   forM xs $ \x -> do
       let !foo_x = foo x
       forM ys $ \y -> do
           let !foo_x_y = foo_x y
           forM zs $ \z -> do
               let !foo_x_y_z = foo_x_y z
               ...

In this example we're performing loop invariant code motion, but doing so dynamically in order to maintain a separation between the definition of foo and its use.

--
Live well,
~wren

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe