haskell 小母牛

前些日子做的一个cow生小牛的问题,一开始有1只cow,每只cow长到4岁后每年可以生一只cow,然后算任意年有多少cow.
用haskell写的程序,第一版:

year1 [y1,y2,y3,y4x] = y1
year2 [y1,y2,y3,y4x] = y2
year3 [y1,y2,y3,y4x] = y3
year4x [y1,y2,y3,y4x] = y4x
cow_group_sum year = sum (group year)
group 1 = [1,0,0,0]
group year = [(year4x (group (year-1))), (year1 (group (year-1))), (year2 (group (year-1))), ((year4x (group (year-1))) + (year3 (group (year -1))))]

这样算来, 因为group函数每次递归都要算4次(4次完全相同的调用), 所以算40年的解已经非常的耗时间了.

避免重复计算需要显式的把group的结果存为临时值, 这样就能避免无意义的多次计算了:

cowsum year = sum (group year)
year1 [y1,_,_,_] = y1
year2 [_,y2,_,_] = y2
year3 [_,_,y3,_] = y3
year4x [_,_,_,y4x] = y4x
group 1 = [1,0,0,0]
group year = [year4x lastyear,
                  year1 lastyear,
                  year2 lastyear,
                  ((year4x lastyear) + (year3 lastyear))]
   where lastyear = group (year -1)


但是,对于函数式编程来说,既然没有副作用, 那么这种优化如果由程序来做其实是完全没问题的. 我还不知道ghc如何才能进行这样的优化