Dusan Kolar
Dlists maybe good it all the app is written using them. Probably not good idea to switch to them in the middle of project...
I know it is lazy, but I don't think it is able to eliminate operations, is it?
At least intuitively, the map f list takes n*C ticks (C is for application of f and list "creation", n is the list length, f is of no importance, it is always the same, but list probably must be created due to ++).
Then, (++) take n*K ticks (K for list creation - I want to write out the list at the end, so that it is created).
In my case (mapapp), it is n*CK, where CK stands for f and list creation... the CK is very similar to C... Thus, I should save the n*K, or at least its large portion... shouldn't I? If not, how the compiler can eliminate the operations? IMHO, the best way to reason about functional programs is via equational reasoning. So let's consider straightforward definitions for map and (++):
map f [] = [] map f (x:xs) = f x : map f xs (++) [] l = l (++) (x:xs) l = x : (xs ++ l) Now let's see what happens with (map f x) ++ y doing case analysis and simplification with the above equations: (map f []) ++ y = [] ++ y = y (map f (x:xs)) ++ y = (f x : map f xs) ++ y = f x : (map f xs ++ y) So: (map f []) ++ y = y (map f (x : xs)) ++ y = f x : (map f xs ++ y) Now consider trivial definition for mapapp: mapapp f x y = (map f x) ++ y. Substituting this backwards into the above equations, we get: mapapp f [] y = y mapapp f (x : xs) y = f x : (mapapp f x xs) which is exactly the definition you've listed. Of course, a Haskell implementation is not *required* to do such transformations, but unless you really observe the difference in performance, it's more or less safe to assume there would be no intermediate list creation/destruction. -- S. Y. A(R). A.