Hal Daume III asked:
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.
If f is associative, i.e. f (l1++l2) == f [f l1, f l2] (this forces a=b), you can do mapWithout :: ([a] -> a) -> [a] -> [a] mapWithout f l = let n = f [] -- neutral element b x y = f [x,y] -- binary version sl = scanl b n l sr = scanr b n l in zipWith b sl (tail sr) You'll probably rather use mapWithout' (a->a->a) -> a -> [a] -> [a] mapWithout' bin_op neutral l = ... If f is not defined for empty lists, you can combine (with a bit more work) the results of scanl1 and scanr1. HTH Christian Sievers