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 |
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 ++ [])) |
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.)
This entry was posted on Wednesday, August 8th, 2007 at 10:52 pm and is filed under Uncategorized. 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.