On Thursday 16 January 2003 08:10 am, 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 (++).
Sometimes, I find it easier to think about problems in C/C++. If I had a list in C, I would simply run f from the head of the list to the current split point, skip this one, then continue until the end of the list. Notice that this gives O(n^2) complexity. It struck me though, if you have a function that calculates something on a list 'lst', and then you calculate something on 'lst ++ [a]', then surely one should be able to cache the results from the previous calculation. For the same reason, if you have calculated f on '[a] + lst', you should be able to calculate the result on 'lst'. For instance, if f = sum, then the basic operation is (+), so your mapWithout function should be equivalent to: mapWithoutSum lst = let tot = sum lst in map (\x -> tot - x) lst So, mapWithout :: ([a] -> b) -> (b -> a -> b) -> [a] -> [b] mapWithout f g lst = let total = f lst in map (g total) lst mapWithoutSum' = mapWithout sum (\total x -> total - x) Perhaps some Haskell expert can expand on this idea? PKE.