[Haskell-beginners] Can ghc compiler Optimize the several calls to Same function

[Daniel Fischer]

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
> <nicholas.ulysses at gmail.com
>
> > 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