[Haskell-cafe] Re: does the compiler optimize repeated calls?

[Sebastian Sylvan]

On 9/6/06, Sebastian Sylvan <sylvan at student.chalmers.se> wrote:
> On 9/6/06, Stephane Bortzmeyer <bortzmeyer at nic.fr> wrote:
> > On Wed, Sep 06, 2006 at 02:12:28PM +0100,
> >  Sebastian Sylvan <sylvan at student.chalmers.se> wrote
> >  a message of 36 lines which said:
> >
> > > I think most compilers actually do CSE
> >
> > And automatic memoization? Because common subexpressions can be
> > difficult to recognize but, at run-time, it is much easier to
> > recognize a function call that has already been done. Any common
> > compiler / interpreter which automatically memoizes? In theory, it is
> > also a huge advantage of "pure" functional programming languages.
>
> Not that I'm aware of. I don't think it's very easy to do well. The
> compiler would have to keep a buffer of input/output pairs for each
> function (even ones which never gets called with the same input twice)
> which eats up memory - it's probably very difficult to statically say
> anything about the frequency of certain inputs to functions so you'd
> have to store caches for every function in the program.
>
> If you have a function with a certain range which is used often, it's
> very easy to do memoization yourself in Haskell (untested!):
>
> import Data.Array
>
> fac n | n <= 100 = facArr ! n
>         | otherwise = fac' n
>         where fac' x = product [1..x]
>                   facArr = listArray (1,100) (map fac' [1..100])
>

Sorry, the facArr needs to be toplevel otherwise it probably won't
retain it's values. So something like:
module Fac (fac) where -- we don't export fac' only fac

import Data.Array
fac n | n <= 100 = facArr ! n
        | otherwise = fac' n

fac' x = product [1..x]
facArr = listArray (1,100) (map fac' [1..100])

-- 
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862