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 (++).
>
>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 following version is probably faster:
mapWithout f [] = []
mapWithout f l = map_without l [] []
where
map_without [e] t t2
= f t:t2
map_without [e1,e2] t t2
= f (e2:t):f (e1:t):t2
map_without l t t2
= map_without l1 (l2++t) (map_without l2 (l1++t) t2)
where
(l1,l2) = splitAt (length l `div` 2) l
Regards,
John van Groningen
_______________________________________________
Haskell mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell
