[Haskell-beginners] Re: Dynamic Programming in Haskell

[Heinrich Apfelmus]

Daniel Fischer wrote:
> On Wednesday 07 July 2010 18:40:07, Ali Razavi wrote:
>> Thanks a lot for your through and informative response. Your solution is
>> well-structured and pellucid. The only part I don't understand is in the
>> definition of Parens:
>>
>>   data Parens     = Mul !Cost Dimension Parens Parens
>>
>>                     | Matrix Dimension deriving (Show)
>>
>> What is the exclamation mark in !Cost, and what does it signify?
> 
> It's a strictness annotation and signifies that a Mul-value must always be 
> constructed with an evaluated Int and not with a reference to a 
> computation.

I.e. a small optimization. It is very common to use this for cached 
values at the branches of a tree.

The idea is that we would like to evaluate the cost early; after all, 
lazy evaluation might build up computations like

    Mul (((0 + 0 + 10*100*5) + 0 + 10*5*50) + 0 + 10*50*1) ...

and only evaluate them at the very end. This might give a stack overflow 
when the expression is large, but since we know that the cost is needed, 
we can evaluate it right away. (This is like  foldl  vs  foldl' )


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com