avoiding cost of (++)

[Zdenek Dvorak]

Hello,

>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.

two remarks:
1) as long as f works on single list, there is no way how to make things
   faster (IMHO)
2) this solution is up to constant factor optimal due to laziness (at most 
one
   step of ++ will be evaluated for each element f needs)

Zdenek Dvorak

_________________________________________________________________
Protect your PC - get McAfee.com VirusScan Online 
http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963