Caching evaluation of lazy lists
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, 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? 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? Any advice greatly appreciated, Philip
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
Hello again,
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).
Thanks Daniel, that was what I was after. Is there any way of investigating these things without using the profiler? E.g. is there any way to stick a debug print statement inside a function without moving over to sideeffects and IO Monads etc.. I know printing is a side effect, but it would be nice to say 'I can has itsy sneeky side effect plz Haskell, just for little testing while' Cheers, Philip
Am Freitag 23 Oktober 2009 18:30:53 schrieb Philip Scott:
Hello again,
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).
Thanks Daniel, that was what I was after. Is there any way of investigating these things without using the profiler? E.g. is there any way to stick a debug print statement inside a function without moving over to sideeffects and IO Monads etc.. I know printing is a side effect, but it would be nice to say 'I can has itsy sneeky side effect plz Haskell, just for little testing while'
Cheers,
Philip
import Debug.Trace infixl 0 `debug` debug = flip trace dfib :: Int -> Integer dfib = let fib 0 = 0 fib 1 = 1 fib n = dfib (n-2) + dfib (n-1) `debug` "eval fib " ++ show n in (map fib [0 .. ] !!) Ok, modules loaded: MFib. *MFib> dfib 4 eval fib 4 eval fib 2 eval fib 3 3 *MFib> dfib 7 eval fib 7 eval fib 5 eval fib 6 13 *MFib> dfib 15 eval fib 15 eval fib 13 eval fib 11 eval fib 9 eval fib 8 eval fib 10 eval fib 12 eval fib 14 610 *MFib> The trick with debug = flip trace makes commenting out the debug-code easier: fun x = trace ("fun " ++ show x) $ body x ~> fun x = {- trace ("fun " ++ show x) $ -} body x vs. fun x = body x `debug` "fun " ++ show x ~> fun x = body x -- `debug` "fun " ++ show x But beware, including the argument in the trace message can lead to recalculation of values which would be cached without it, it's a hairy issue.
participants (3)
-
Daniel Fischer -
Philip Scott -
Philip Scott