{"id":25,"date":"2007-07-28T21:37:21","date_gmt":"2007-07-29T04:37:21","guid":{"rendered":"http:\/\/www.elbeno.com\/haskell_soe_blog\/?p=25"},"modified":"2008-01-07T22:06:35","modified_gmt":"2008-01-08T06:06:35","slug":"exercise-71","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/haskell_soe_blog\/?p=25","title":{"rendered":"Exercise 7.1"},"content":{"rendered":"<pre lang=\"haskell\">data Tree a = Leaf a\r\n            | Branch (Tree a) (Tree a)\r\n              deriving Show\r\n\r\nfoldTree :: (a -> b -> b) -> (b -> b -> b) -> b -> Tree a -> b\r\nfoldTree fLeaf _ init (Leaf x) = fLeaf x init\r\nfoldTree fLeaf fBranch init (Branch x y) = fBranch x' y'\r\n    where x' = foldTree fLeaf fBranch init x\r\n          y' = foldTree fLeaf fBranch init y\r\n\r\nfringe :: Tree a -> [a]\r\nfringe t = foldTree (:) (++) [] t\r\n\r\ntreeSize :: Tree a -> Int\r\ntreeSize t = foldTree (\\x y -> 1 + y) (+) 0 t\r\n\r\ntreeHeight :: Tree a -> Int\r\ntreeHeight t = foldTree (\\x y -> 0) (\\x y -> 1 + max x y) 0 t<\/pre>\n<p>The key to a tree fold was realising that two functions were needed: one for leaves and one for branches. In general, I think any fold would require a function per constructor for the data structure it works on.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>data Tree a = Leaf a | Branch (Tree a) (Tree a) deriving Show foldTree :: (a -> b -> b) -> (b -> b -> b) -> b -> Tree a -> b foldTree fLeaf _ init (Leaf x) = fLeaf x init foldTree fLeaf fBranch init (Branch x y) = fBranch x&#8217; y&#8217; [&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\/25"}],"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=25"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=\/wp\/v2\/posts\/25\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=25"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=25"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/haskell_soe_blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=25"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}