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