[Haskell-cafe] How to think about this? (profiling)

[Thorkil Naur]

Hello,

On Tuesday 16 December 2008 13:19, Felipe Lessa wrote:
> 2008/12/16 Magnus Therning <magnus at therning.org>:
> > That is, where each value depends on _all_ preceding values.  AFAIK
> > list access is linear, is there a type that is a more suitable state
> > for this changed problem?
> >
> > I realise this particular function can be written using scanl:
> [...]
> > but I guess it's not always that easy to construct a solution based on 
scanl.
> 
> 
> You can always write something like
> 
> > foo :: Int -> Int
> > foo = (vals !!)
> >     where
> >     vals = map foo' [0..]
> >     foo' 0 = 0
> >     foo' 1 = 1
> >     foo' 2 = 2
> >     foo' n = sum $ map foo [0..n-1]
> 
> which doesn't prevent you from using whatever recursive case you want.
> Note that if your recursive case depends on all preceding values, then
> you can't do better than using a linear access data structure like a
> list unless you need random access.

Another possibility would be:

> g n = t!n
>   where
>   t = array
>       (0,max 2 n)
>       $ (0,0):(1,1):(2,2):[ (i,t!(i-3) + t!(i-2) + t!(i-1)) | i <- [3..n] ]    

using your original example. As noted in the Haskell 98 report, section 16.1 
Array Construction, the array function is non-strict in the values of the 
association list, making this recurrence possible.

> ...

Best regards
Thorkil