[Haskell-cafe] Library function for map+append
Artem V. Andreev
artem at AA5779.spb.edu
Tue Aug 18 08:55:10 EDT 2009
Dusan Kolar <kolar at fit.vutbr.cz> 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.
More information about the Haskell-Cafe
mailing list