[Haskell-beginners] Caching evaluation of lazy lists

Daniel Fischer daniel.is.fischer at web.de
Fri Oct 23 09:08:03 EDT 2009


Am Freitag 23 Oktober 2009 13:51:52 schrieb Philip Scott:
> Hi folks,
>
> Quick question for you. Suppose I have some lazy list, x, which is very
> expensive to evaluate, and I want to do something with it more than
> once; for example:
>
> f x = g (take 5 x) (take 6 x)
>
> Is Haskell clever enough to only evaluate the list as much as is needed,

In that example, when you call "f (makeExpensiveList arg1 arg2)", the list is bound to the 
name x in the body of f, so g's arguments are taken from the very same list, which is 
evaluated only once. Each of the list elements is evaluated when it's needed, so maybe 
there will be fewer than 6 elements evaluated.
However, if you call "f (makeExpensiveList arg1 arg2)" again later in the programme with 
the same arg1 and arg2, it will be probably evaluated again (the optimiser would need to 
see that it's called with the same arguments again and that it's worth caching the result 
to avoid that).

If your expensive list is not generated by a function but a constant (like the list of 
Fibonacci numbers), bind it to a name

expensiveList = ...

and it will be cached between calls to f (unless memory pressure forces it to be garbage 
collected between calls and then re-evaluated).
If it's generated by a function, give names to the lists obtained from frequently used 
arguments:

exList_1_2 = makeExpensiveList 1 2
exList_4_0 = makeExpensiveList 4 0
...

cachedExpensiveList 1 2 = exList_1_2
cachedExpensiveList 4 0 = exList_4_0
...
cachedExpensiveList a b = makeExpensiveList a b


> or will it evaluate it once to get the first five values, and again to
> get the first 6 (when really it only needed to get one more). Or is it
> really really clever, and works out it needs to take 6 to begin with,
> then just give you the first 5 for the first call?

The order of evaluation is determined by data-dependencies, so it may evaluate the list in 
order, or evaluate the sixth element first, then the first, after that the third,...

>
> More tricky - is there a way to make that cache (if it exsists) persist
> in an interactive session? Eventually I am intending to write my own
> application with a little console at the bottom which does some
> ghci-esque magic, but for now lets say I am in ghci and I want to call f
> again with the same list. Is there a way to avoid it from forcing a
> recomputation of my lazy list?

Give it a name:

let el = makeExpensiveList args

then, barring memory pressure forcing it out, it will be computed only once (each list 
element will be computed only once, when it's first needed).

>
> Any advice greatly appreciated,
>
> Philip




More information about the Beginners mailing list