I just wrote a tiny little Haskell program that demonstrates a small trick: how to use an infinite global constant to speed up tree-recursive functions. Remove .html from it’s URL to download an executable Haskell file.

comments on reddit

more comments

My code shows how to speed up naive recursive algorithms without changing their basic structure. John Tromp has sent me a one liner that computes the table of binomial coefficients by iteration:

iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]