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

[nicholas.ulysses]

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
_______________________________________________
Beginners mailing list
Begi...@haskell.org
http://www.haskell.org/mailman/listinfo/beginners

[edgar klerks]

Hi Nicholas,

If you use a where statement, 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.

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

Greets,

Edgar

[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.