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. To reduce the complexity involved with creating automata trees, lets define a very simple function: module Memo () where calc :: Integer -> Integer calc = (1+) 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 You can literally watch things slowing down as new values are being printed. As you said correctly, at every call to `ints` the whole list is recalculated up to the value you need. Since `ints` is called with a new parameter at every iteration, Haskell has no way of memoizing anything. 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. `is` has type [Integer] and as such is a constant. Already calculated values of `is` will therefore be memoized, so the whole list is only created once. Still, this is far from ideal. Enter ints2 1 !! 50000 and wait some more. The problem is that the algorithm still has O(n^2) complexity, n being the length of the list you need to create. At every iteration, `is !! (n-1)` accesses the (n-1)th element of `is` which takes itself n-1 operations. So, to generate a list of ten elements, the algorithm runs is !! 1 is !! 2 . . . is !! 9 to a total of 45 operations. For small list sizes, this makes hardly a difference, but for a list size of 50'000, this means already 1'249'975'000 operations doing nothing but traversing a list. Let's improve this further: ints3 :: Integer -> [Integer] ints3 i = i : ints3 (calc i) Here we use Haskell's lazyness to great effect. This function says: our list of ints is the initial value, prepended to the list of ints starting at the next value. take 500 $ ints3 1 and ints3 1 !! 50000 are both very fast. Every item in the list is calculated exactly once and the algorithm runs in linear time. Now you will only run into trouble at very large indices (above 10'000'000 on my computer). `ints3` is not tail recursive and will produce a stack overflow for very large lists. When you look at the source code of `iterate` you will see that it is just a generalized version of `ints3` taking an additional higher order function as input. I hope this sheds some light Stefan