avoiding cost of (++)

[John van Groningen]

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 (++).
>
>Any way I could speed this up would be great.  Note that order doesn't
>matter to 'f', but I do need that the order in which the elements of the
>list are processed be the same as in map.

The following version is probably faster:

mapWithout f [] = []
mapWithout f l = map_without l [] []
 	where
	   map_without [e] t t2
		    = f t:t2
	   map_without [e1,e2] t t2
		    = f (e2:t):f (e1:t):t2
	   map_without l t t2
		    = map_without l1 (l2++t) (map_without l2 (l1++t) t2)
		    where
			     (l1,l2) = splitAt (length l `div` 2) l

Regards,

John van Groningen