avoiding cost of (++)

[Adrian Hey]

On Thursday 16 January 2003  4:10 pm, you 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 (++).

As an alternative to ++ I often use something like this..
 -- revJoin xs ys = (reverse xs) ++ ys
 revJoin []     ys = ys
 revJoin (x:xs) ys = revJoin xs (x:ys)

Which my intuition tells me will be faster overall because it avoids the
construction of thunks and the imperative (tail recusive) style probably
gives more cache friendly code. Of course whether or not this really is
better depends on context it's used. In your case using revJoin would
undo the reversal of pre in mapWith' (which may or may not be a good thing)
  
Regards
--
Adrian Hey