avoiding cost of (++)

[Janis Voigtlaender]

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 (++).

The following version avoids concatenations:

 mapWithout :: ([a] -> b) -> [a] -> [b]
 mapWithout f []     = []
 mapWithout f (x:xs) = f xs : mapWithout (\ys -> f (x:ys)) xs

but I doubt that you will see much speedup. 

> 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 problem is that creating the "list of all sublists with one element
dropped" is inherently of quadratic complexity (or so I think...)
Nice puzzle though: how to minimize constant factors?

Cheers, Janis.


--
Janis Voigtlaender
http://wwwtcs.inf.tu-dresden.de/~voigt/
mailto:voigt@tcs.inf.tu-dresden.de