On Thu, 16 Jan 2003, 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 (++).
I don't think this can be sped up appreciably without avoiding the construction of the lists pre++xs. To accomplish that, I would change the type of mapWithout, as follows: mapPrePost :: ([a] -> [a] -> b) -> [a] -> [b] mapPrePost f = mapWith' [] where mapWith' pre [] = [] mapWith' pre (x:xs) = f pre xs : mapWith' (x:pre) xs OK, you have to change the functions passed as f, and if f REALLY needs to compute pre++xs then there is no gain, but I'm betting that in many cases f has some property that enables f' pre xs = f (pre++xs) to be computed by a more efficient method. John