[Haskell-cafe] Haskell and "memoization"

Daniel Fischer daniel.is.fischer at web.de
Wed Dec 16 01:19:15 EST 2009


Am Mittwoch 16 Dezember 2009 05:47:20 schrieb Gregory Crosswhite:
> On Dec 15, 2009, at 8:28 PM, Daniel Fischer wrote:
> > Am Mittwoch 16 Dezember 2009 05:08:39 schrieb Gregory Crosswhite:
> >
> > Not even then, necessarily. And it's not always a good idea.
> >
> > f k = [1 .. 20^k]
>
> You raise a really good point here.  One can force sharing, as I understand
> it, by using a let clause:
>
> n =
> 	let xs = f 20
> 	in length (xs ++ xs)
>
> If I understand correctly, this should cause xs to be first evaluated,

It is evaluated during the calculation of the length. But whereas in

n = let xs = f 20
        ys = f 10
    in length (xs ++ ys)

every cell of xs can be immediately garbage collected - so it will only take insanely long 
to get a result -, in the above example the scond argument of (++) holds on to xs, so they 
can't be garbage collected (I wouldn't bet any body parts on that, an implementation is 
allowed to recalculate a named entity on every occurrence, but it's the expected 
behaviour) and you will run into memory problems. The good part of it is that it finishes 
much faster :)

> and then cached until the full length is computed, which in this case is
> obviously undesirable behavior.
>
> Cheers,
> Greg



More information about the Haskell-Cafe mailing list