avoiding cost of (++)

[Christian Sievers]

Hal Daume III asked:

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

If f is associative, i.e.  f (l1++l2) == f [f l1, f l2]
(this forces a=b), you can do

mapWithout :: ([a] -> a) -> [a] -> [a]
mapWithout f l = let n  = f []         -- neutral element
                     b x y = f [x,y]   -- binary version
                     sl = scanl b n l
                     sr = scanr b n l
                 in zipWith b sl (tail sr)

You'll probably rather use
mapWithout' (a->a->a) -> a -> [a] -> [a]
mapWithout'  bin_op   neutral  l = ...

If f is not defined for empty lists, you can combine (with a bit more work)
the results of scanl1 and scanr1.


HTH
Christian Sievers