avoiding cost of (++)

[Hal Daume III]

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.

 - Hal

--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume