{"id":48,"date":"2007-08-08T22:52:18","date_gmt":"2007-08-09T05:52:18","guid":{"rendered":"http:\/\/www.elbeno.com\/haskell_soe_blog\/?p=48"},"modified":"2008-01-08T09:57:23","modified_gmt":"2008-01-08T17:57:23","slug":"exercise-96","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/haskell_soe_blog\/?p=48","title":{"rendered":"Exercise 9.6"},"content":{"rendered":"<pre lang=\"haskell\">appendr = foldr (flip (++)) []\r\nappendr [x,y,z]\r\n= foldr (flip (++)) [] [x,y,z]\r\n= flip (++) x (flip (++) y (flip (++) z []))\r\n= flip (++) x (flip (++) y ([] ++ z))\r\n= flip (++) x (([] ++ z) ++ y)\r\n= (([] ++ z) ++ y) ++ x<\/pre>\n<p>Running time of <tt>appendr<\/tt> is O(n<sup>2<\/sup>) since <tt>(++)<\/tt> traverses the length of its first argument.<\/p>\n<pre lang=\"haskell\">appendl = foldl (flip (++)) []\r\nappendl [x,y,z]\r\n= foldl (flip (++)) [] [x,y,z]\r\n= flip (++) (flip (++) (flip (++) [] x) y) z\r\n= flip (++) (flip (++) (x ++ []) y) z\r\n= flip (++) (y ++ (x ++ [])) z\r\n= z ++ (y ++ (x ++ []))<\/pre>\n<p>Running time of <tt>appendl<\/tt> is O(n).<\/p>\n<p>(<a href=\"http:\/\/haskell.org\/soe\/Bug\/erata.htm\">Technical error 16<\/a> applies to this exercise.)<\/p>\n","protected":false},"excerpt":{"rendered":"<p>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 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=\/wp\/v2\/posts\/48"}],"collection":[{"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=48"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=\/wp\/v2\/posts\/48\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=48"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=48"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=48"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}