avoiding cost of (++)

[Gerhard Navratil]

If we can remove the effect of a single element we can reduce the number
of reductions significantly:

mapWithout2 :: ([a] -> a) -> ((a,a) -> a) -> [a] -> [a]
mapWithout2 f1 f2 l =3D map f2 list
  where list =3D zip (replicate (length l) (f1 l)) l

I only made the simplification the have a single data type so I could
use the following example for testing:

mw2 =3D mapWithout2 sum (uncurry (-)) (take 100 [1..])

Of course the code can be optimized but I usually do not care about
performnance issues ...

Gerhard

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
Gerhard Navratil
Teaching- And Research-Assistant

Vienna University of Technology, Austria
Institute for Geoinformation

Gusshausstr. 27-29
1040 Vienna

Tel.: ++43 (0) 1 / 58 801 - 12721
Fax.: ++43 (0) 1 / 58 801 - 12799
Cel.: ++43 (0) 699 / 197 44 761
http://www.geoinfo.tuwien.ac.at


-----Original Message-----
From: haskell-admin@haskell.org [mailto:haskell-admin@haskell.org] On
Behalf Of Hal Daume III
Sent: Donnerstag, 16. J=E4nner 2003 17:11
To: Haskell Mailing List
Subject: avoiding cost of (++)


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 =3D mapWith' []
>     where mapWith' pre [] =3D []
>           mapWith' pre (x:xs) =3D 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.

 - Hal

--
Hal Daume III

 "Computer science is no more about computers    | hdaume@isi.edu
  than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume


_______________________________________________
Haskell mailing list
Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell