After paraphrasing a computation I had found in a paper, I realized I had ruined its performance.
The pathological version:
part0 = 1 : b 1
where b n = zipWith (+) (1 : b (n + 1)) (replicate n 0 ++ b n)
The original version:
part = 1 : b 1
where b n = p where p = zipWith (+) (1 : b (n + 1)) (replicate n 0 ++ p)
See the difference in performance:
ghci> :set +s
ghci> take 35 part0
[1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310]
(0.20 secs, 101,561,000 bytes)
ghci> take 35 part
[1,1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627,792,1002,1255,1575,1958,2436,3010,3718,4565,5604,6842,8349,10143,12310]
(0.01 secs, 280,656 bytes)
This is because p in the original version is shared, while b n is not.
Hopefully the above is a good example of laziness/sharing, by crossing the border of sensible use, we have proved the method works!
