avoiding cost of (++)

[John Hughes]

On Thu, 16 Jan 2003, Hal Daume III wrote:

> I have a function which behaves like map, except instead of applying the
> given function to, say, the element at position 5, it applies it to the
> entire list *without* the element at position 5.  An implementation looks
> like:
>
> > mapWithout :: ([a] -> b) -> [a] -> [b]
> > mapWithout f = mapWith' []
> >     where mapWith' pre [] = []
> >           mapWith' pre (x:xs) = f (pre ++ xs) : mapWith' (x:pre) xs
>
> Unfortunately, this is very slow, due to the overhead of (++).
>

I don't think this can be sped up appreciably without avoiding the
construction of the lists pre++xs. To accomplish that, I would change the
type of mapWithout, as follows:

mapPrePost :: ([a] -> [a] -> b) -> [a] -> [b]
mapPrePost f = mapWith' []
  where mapWith' pre [] = []
	mapWith' pre (x:xs) = f pre xs : mapWith' (x:pre) xs

OK, you have to change the functions passed as f, and if f REALLY needs to
compute pre++xs then there is no gain, but I'm betting that in many cases
f has some property that enables

	f' pre xs = f (pre++xs)

to be computed by a more efficient method.

John