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:[EMAIL PROTECTED] | a Special Outdoor Song which Has To Be work tel:(0117) 954-5250 | Sung In The Snow' -- Winnie the Pooh _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell