Dusan Kolar <[email protected]> writes:
> 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.
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
