appendr = foldr (flip (++)) []
appendr [x,y,z]
= foldr (flip (++)) [] [x,y,z]
= flip (++) x (flip (++) y (flip (++) z []))
= flip (++) x (flip (++) y ([] ++ z))
= flip (++) x (([] ++ z) ++ y)
= (([] ++ z) ++ y) ++ x
Running time of appendr is O(n2) since (++) traverses the length of its first argument.
appendl = foldl (flip (++)) []
appendl [x,y,z]
= foldl (flip (++)) [] [x,y,z]
= flip (++) (flip (++) (flip (++) [] x) y) z
= flip (++) (flip (++) (x ++ []) y) z
= flip (++) (y ++ (x ++ [])) z
= z ++ (y ++ (x ++ []))
Running time of appendl is O(n).
(Technical error 16 applies to this exercise.)