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