[Haskell-beginners] Haskell Bin Tree Cellular Automata.

[Henk-Jan van Tuyl]

'iterate' uses optimization techniques, see the source code[0][1] (click  
the 'source' links). I didn't study these techniques in detail.

[0]  
http://haddocks.fpcomplete.com/fp/7.8/20140916-162/base/Prelude.html#v:iterate
[1]  
http://haddocks.fpcomplete.com/fp/7.8/20140916-162/base/GHC-Exts.html#v:build



On Fri, 05 Jun 2015 01:31:07 +0200, Sourabh <sourabh.s.joshi at gmail.com>  
wrote:

> Wow, it runs in 0.44 seconds now. This is incredible! Can you explain  
> what
> just happened here?
>
> On Thu, Jun 4, 2015 at 4:28 PM, Henk-Jan van Tuyl <hjgtuyl at chello.nl>  
> wrote:
>
>> On Fri, 05 Jun 2015 00:50:25 +0200, Sourabh <sourabh.s.joshi at gmail.com>
>> wrote:
>>
>>  I figured out that I am constantly re-computing the trees, and decided  
>> to
>>> try and memoize the results. Here is my memoization attempt:
>>>
>>> https://github.com/cbrghostrider/Hacking/blob/master/HackerRank/FunctionalProgramming/Recursion/cellular_automata_memoize_attempt.hs
>>>
>>> Basically I have changed the simulateCellularAutomata function, which
>>> computed the new trees, into a list (automataTrees - line 60).  I was
>>> expecting the results to be memoized, but the runtime is unchanged.
>>>
>>
>> At a glance: maybe if you change the line
>>   automataTrees starttree rule = (starttree) : [ simulateAutomataStep
>> Nothing rule ((automataTrees starttree rule) !! (n-1)) | n <- [1..]]
>> to
>>   automataTrees starttree rule = iterate (simulateAutomataStep Nothing
>> rule) starttree
>> it will run faster. The function 'iterate' can be found in Prelude and
>> Data.List.
>>
>> Regards,
>> Henk-Jan van Tuyl

-- 
Folding at home
What if you could share your unused computer power to help find a cure? In  
just 5 minutes you can join the world's biggest networked computer and get  
us closer sooner. Watch the video.
http://folding.stanford.edu/