[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)

(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