[Haskell-beginners] Haskell Bin Tree Cellular Automata.

[Frerich Raabe]

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 at froglogic.com
www.froglogic.com - Multi-Platform GUI Testing