On Thursday 11 November 2010 01:40:18, edgar klerks wrote:

Hi Nicholas,

If you use a where statement,

Or a let binding, whatever one prefers.

GHC only has to compute the computation group year once, because it can be shared.

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)

--look here-- group 1 = [1,0,0,0] group (year+1) = [year4x gy, year1 gy,year2 gy,year4x gy + year3 gy] where gy = group year

main = print (cow_group_sum 50)

This works a lot faster.

That, or group (year+1) = case group year of [y1,y2,y3,y4x] -> [y4x,y1,y2,y4x+y3] _ -> error "oops" Note, however, that (n+k)-patterns have been removed in Haskell2010, so the code won't compile with the next GHC unless you turn on the NPlusKPatterns extension.

I don't understand why GHC doesn't pick this up.

GHC does very little common subexpression elimination (CSE). The reason is that CSE can have disastrous effects, as sharing can lead to huge memory requirements (imagine sharing a loong list for example). Unconditionally doing CSE is hence not an option, and finding out when sharing will be beneficial and when it will be detrimental is very hard (possibly impossible in general). So it's basically left to the programmer to decide when to share. Give it a name and it will be shared, otherwise probably not.

Greets,

Edgar On Mon, Nov 8, 2010 at 2:08 PM, nicholas.ulysses

...

wrote:

It's my code to do some recursive things, focus on function 'group'.

---- cow.hs 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)

--look here-- group 1 = [1,0,0,0] group (year+1) = [(year4x (group year)), (year1 (group year)), (year2 (group year)), ((year4x (group year)) + (year3 (group year)))]

main = print (cow_group_sum 50) ---- end

Every time 'group' was called, the (group year) function was called 4 times . when call (group 30), it takes tens seconds to finish.

I have tried 'ghc -O3', but it's still 'lazy' on this thing.

Map-Reduce seems to be the answer to the question. But I want to make sure that ghc CAN or CANNOT do the Optimize for Dynamic Programming?

---------------- xingbo wu