David Tran’s blog

appendr, appendl :: [[a]] -> [a]
appendr = foldr (flip (++)) []
appendl = foldl (flip (++)) []

(~++) :: [a] -> [a] -> [a]
(~++) = flip (++)

{-
Prelude.hs  defined (++) as:
(++)             :: [a] -> [a] -> [a]
[]     ++ ys      = ys
(x:xs) ++ ys      = x : (xs ++ ys)


So, let's exam:

   appendr [a1, a2, a3]
=  a1 ~++ ( a2 ~++ ( a3 ~++ [] ) )
=  ( ( [] ++ a3 ) ++ a2 ) ++ a1
===>  recursive called (++):  [] ++ a3   ==> 0 time
                              ([] ++ a3) ++ a2  ==> length of a3 times
                              (([] ++ a3) ++ a2) ++ a1  ==> length of (a3)+a3+a2 times

   appendl [a1, a2, a3]
=  ( ( [] ~++ a1 ) ~++ a2 ) ~++ a3
=  a3 ++ ( a2 ++ ( a1 ++ [] ) )
===>  recursive called (++):   a1 ++ []   ==> length of a1 times
                               a2 ++ (a1 ++ [])  ==> length of (a1)+a2 times
                               a3 ++ (a2 ++ (a1 ++ []))  ==> length of (a1+a2)+a3 times

To generalize:

appendl [a1, a2, ..., an]
= an ++ (an-1 ++ (an-2 ++ ...... ++ (a1 ++ []) ....))
====>  an + an-1 + an-2 + .... + a2 + a1
     = SUM (for i=1..n) (li)  times call (++) recursive; where li = length of ai

appendr [a1, a2, ..., an]
= (...([] ++ an) ++ an-1) ++ an-2) ++ ......) ++ a1
====>     0
             an
             an  +  an-1
             an  +  an-1  +  an-2
 ...
             an  +  an-1  +  an-2  + ...+ a3
             an  +  an-1  +  an-2  + ...+ a3 + a2
====>  an * (n-1) + an-1 * (n-2) + .... + a3 * 2 + a2 * 1
     = SUM (for i=1..n) (li * (i-1)) times call (++) recursive; where li = length of ai


So, appendl is much more efficient than appendr!

-}

This entry was posted on Wednesday, June 6th, 2007 at 5:18 pm and is filed under Haskell - SOE. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.