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 _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell