avoiding cost of (++)

[Iavor S. Diatchki]

hi,

just for fun i wrote the function in a different way.  it should perform 
pretty much the same way as your function.  i don't think the problem is 
(++) here, it is just the way this function is.  if "f" is going to use 
all of its argument, it doesn't matter that you concatenated the two 
lists, as you will be walking over the list anyways.  if it is going to 
use only the first few elements, than becasue of lazyness (++) doesn't 
matter again.  you could avoid the linear concatenation by just using 
"zip" instead of "zipWith (++)" and making "f" take a pair of 
(before,after) elements, but as i said i don't see how that will speed 
up things, unless of course "f" wanted to, say only process the "after" 
elements.

import List(inits,tails)

mapWithout f [] = []
mapWithout f xs = map f (zipWith (++) (inits xs) (tails (tail xs)))

hope this helped
iavor


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


-- 
==================================================
| Iavor S. Diatchki, Ph.D. student               |
| Department of Computer Science and Engineering |
| School of OGI at OHSU                          |
| http://www.cse.ogi.edu/~diatchki               |
==================================================