On 2015-06-06 06:01, Stefan Höck wrote:
On Thu, Jun 04, 2015 at 04:31:07PM -0700, Sourabh wrote:
Wow, it runs in 0.44 seconds now. This is incredible! Can you explain what just happened here?
Here is a try at an explanation.
Thank you a lot for taking the time to walk through it! One thing got me thinking though:
And now we build a list of integers in a similar fashion to your tree-generating function:
ints :: Integer -> [Integer] ints i = i : [calc (ints i !! (n-1)) | n <- [1..]]
Store this in a file, fire up ghci, load the file and enter
take 500 $ ints 1
[..]
Let's add some memoization:
ints2 :: Integer -> [Integer] ints2 i = let is = i : [calc (is !! (n-1)) | n <- [1..]] in is
Again, load this in ghci and run
take 500 $ ints2 1
Marvel at the difference.
This is what's known as 'Tying the Knot' (e.g. on https://wiki.haskell.org/Tying_the_Knot), right? I wonder - would it be possible (and plausible) for a compiler to perform this rewriting automatically, such that any occurrence of code like f x = e where 'e' involves a call to 'f x' gets replaced with f x = let z = e in z and all occurences of 'f x' in 'e' get replaced with 'z'? -- Frerich Raabe - raabe@froglogic.com www.froglogic.com - Multi-Platform GUI Testing