avoiding cost of (++)

[D. Tweed]

On Thu, 16 Jan 2003, Pal-Kristian Engstad wrote:

> It struck me though, if you have a function that calculates something on a
> list 'lst', and then you calculate something on 'lst ++ [a]', then surely one
> should be able to cache the results from the previous calculation.

I'm not a Haskell expert, but the code idea I posted (which was missing a
couple of arguments representing the initial `internal value's) was based
on a variant of this idea, namely move forward through the list producing
`internal values' (I'm trying to avoid using the phrase `internal state'
:-) )  for all prefixes of the list, then do the same for all the suffixes
of the list and combine the state for the prefix ending just before the
omitted item and the suffix beginning just after the omitted item to get a
full result. AFAICS this is O(n), whereas just doing prefixes this way
appears to still be quadratic because of the repeated evaluations of the
tail of the list.

Obviously being able to do this places some restrictions on what f can be
though.

___cheers,_dave_________________________________________________________
www.cs.bris.ac.uk/~tweed/  |  `It's no good going home to practise
email:tweed@cs.bris.ac.uk  |   a Special Outdoor Song which Has To Be
work tel:(0117) 954-5250   |   Sung In The Snow' -- Winnie the Pooh