{"id":339,"date":"2007-07-17T03:35:00","date_gmt":"2007-07-17T10:35:00","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=339"},"modified":"2007-07-29T12:37:51","modified_gmt":"2007-07-29T19:37:51","slug":"more-on-tree-folds","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=339","title":{"rendered":"More on Tree Folds"},"content":{"rendered":"

After some thought, I think I have the definitions for left and right fold on a tree:<\/p>\n

foldrTree :: (a -> b -> b) -> b -> InternalTree a -> b\r\nfoldrTree f z ILeaf = z\r\nfoldrTree f z (IBranch a x y) = foldrTree f (f a (foldrTree f z y)) x\r\n\r\nfoldlTree :: (a -> b -> a) -> a -> InternalTree b -> a\r\nfoldlTree f z ILeaf = z\r\nfoldlTree f z (IBranch a x y) = foldlTree f (f (foldlTree f z x) a) y<\/pre>\n
Of course, these folds are simplified: they don’t have a separate function for dealing with leaves and branches. This leads to things like flatten<\/tt> only working one way, i.e.
\nfoldrTree (:) [] t<\/tt>
\nworks because (:)<\/tt> will accumulate values onto a list properly from the right, but
\nfoldlTree (:) [] t<\/tt>
\ngives a type error (because (:)<\/tt> cannot append a value onto a list working from the left).<\/p>\n","protected":false},"excerpt":{"rendered":"
After some thought, I think I have the definitions for left and right fold on a tree: foldrTree :: (a -> b -> b) -> b -> InternalTree a -> b foldrTree f z ILeaf = z foldrTree f z (IBranch a x y) = foldrTree f (f a (foldrTree…<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-339","post","type-post","status-publish","format-standard","hentry","category-haskell"],"_links":{"self":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/339","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=339"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/339\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=339"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=339"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=339"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}