import Data.Array
f :: Integer -> Integer
f n = sum [0..n]
largeNumber = round 2e6 :: Integer
memo_f :: Array Integer Integer
memo_f = listArray (0,largeNumber) [ (f n) | n <- [0..largeNumber] ]
main = do
putStrLn (show (memo_f!largeNumber)) -- slow
putStrLn (show (memo_f!(largeNumber-1))) -- slow
putStrLn (show (memo_f!(largeNumber))) -- fast
putStrLn (show (memo_f!(largeNumber-1))) -- fast
putStrLn (show (memo_f!(largeNumber-2))) -- slow
putStrLn (show (memo_f!(largeNumber-3))) -- slow
putStrLn (show (memo_f!(largeNumber))) -- fast
putStrLn (show (memo_f!(largeNumber-2))) -- fast
putStrLn (show (memo_f!(largeNumber-4))) -- slow
putStrLn (show (memo_f!(largeNumber-5))) -- slow
When I run this, I see nothing for about 3 seconds (that's the time spent setting up the array). Then the numbers commented '-- slow' take about 1/3 second to print, while the numbers commented '--fast' print instantaneously, because they were calculated previously. (I'm on a recent macbook air, in case anyone's curious about the timings). Obviously to calculate the entire array of values would take far too long (like a week or so).By that logic, implementing Lisp is "a phD-level task", too. (http://repository.readscheme.org/ftp/papers/orbit-thesis.pdf) (http://www.cs.indiana.edu/~dyb/papers/3imp.pdf) (http://repository.readscheme.org/ftp/papers/ai-lab-pubs/AITR...) *
* The third is actually a masters thesis, but whatever.
("How do you implement lazy evaluation in Haskell? No, like, in an application...")
(Personally, I have done this a number of times. I remember writing some dependency evaluation system, with a central data structure that looked something like:
data Dependency a e = Thunk (e -> a) | Resolved a
with a bunch of code to turn a set of Thunks into Resolved when necessary.But of course, Haskell always does this anyway!)
I was also surprised when I was on Windows and needed the "head" utility to look at the first line of a file, but didn't have it installed. Since I had a ghci session going, I just wrote:
readFile "foo.csv" >>= putStrLn . unlines . take 10 . lines
Half-expecting it to error out because the file didn't fit into memory. Nope! Problem solved!(And yes, I know unsafeInterleaveIO is evil.)
For example, imagine you need to calculate a function f(n) for various values of n (let's say for n ranging from 0 to N). You simply define an array memo_f such that memo_f!n = f(n). ('!' is the array selection operator in Haskell).
Because Haskell evaluates lazily (i.e. not until it absolutely has to), it simply stores a link to the definition of the function for each array element. But once a particular array element is used, that link is replaced by the calculated answer.
I'll post some actual code to demonstrate this in a minute, just in case anyone's interested.