avoiding cost of (++)

[D. Tweed]

On Thu, 16 Jan 2003, Iavor S. Diatchki wrote:

> hi,
>
> just for fun i wrote the function in a different way.  it should perform
> pretty much the same way as your function.  i don't think the problem is
> (++) here, it is just the way this function is.  if "f" is going to use
> all of its argument, it doesn't matter that you concatenated the two
> lists, as you will be walking over the list anyways.  if it is going to

The other obvious thing to ask is, given you say f doesn't care about the
order of its arguments, is whether you can write a version of f (f', say)
which `outputs its intermediate internal values' and another function
combineFStates which takes in two `internal values' and takes them to a
complete solution. Then at its very simplest (and very untested)

buildPartResults s f' [] = []
buildPartResults s f' (x:xs) = let e=f' s x
                               in e:buildPartResults e f' xs

mapWithout combineFStates f' xs = zipWith combineFStates xs' (tail xs'')
 where xs'=buildPartResults f' xs
       xs''=buildPartResults f (reverse xs)

AFAICS this reuses the partial evaluations of f which, as Iavor suggests,
are likely to be very significant if the lists are long enough that the ++
shows up as costly. Obviously this won't help if f _isn't_ something where
internal states can be updated incrementally or the combining step isn't
easy.

Just a vague thought,

___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