avoiding cost of (++)

[Pal-Kristian Engstad]

On Thursday 16 January 2003 08:10 am, 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 (++).

Sometimes, I find it easier to think about problems in C/C++. If I had a list 
in C, I would simply run f from the head of the list to the current split 
point, skip this one, then continue until the end of the list.

Notice that this gives O(n^2) complexity.

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. 

For the same reason, if you have calculated f on '[a] + lst', you should be 
able to calculate the result on 'lst'.

For instance, if f = sum, then the basic operation is (+), so your mapWithout 
function should be equivalent to:

mapWithoutSum lst = let tot = sum lst in map (\x -> tot - x) lst

So, 

mapWithout :: ([a] -> b) -> (b -> a -> b) -> [a] -> [b]
mapWithout f g lst = 
	let total = f lst in
	map (g total) lst

mapWithoutSum' = mapWithout sum (\total x -> total - x)

Perhaps some Haskell expert can expand on this idea?

PKE.