If we can remove the effect of a single element we can reduce the number of reductions significantly: mapWithout2 :: ([a] -> a) -> ((a,a) -> a) -> [a] -> [a] mapWithout2 f1 f2 l = map f2 list where list = zip (replicate (length l) (f1 l)) l I only made the simplification the have a single data type so I could use the following example for testing: mw2 = mapWithout2 sum (uncurry (-)) (take 100 [1..]) Of course the code can be optimized but I usually do not care about performnance issues ... Gerhard ======================================== Gerhard Navratil Teaching- And Research-Assistant Vienna University of Technology, Austria Institute for Geoinformation Gusshausstr. 27-29 1040 Vienna Tel.: ++43 (0) 1 / 58 801 - 12721 Fax.: ++43 (0) 1 / 58 801 - 12799 Cel.: ++43 (0) 699 / 197 44 761 http://www.geoinfo.tuwien.ac.at -----Original Message----- From: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org] On Behalf Of Hal Daume III Sent: Donnerstag, 16. Jänner 2003 17:11 To: Haskell Mailing List Subject: avoiding cost of (++) 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 (++). 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. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume@isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell