[Haskell-cafe] Library function for map+append

[Artem V. Andreev]

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.