{"id":338,"date":"2007-07-16T02:49:00","date_gmt":"2007-07-16T09:49:00","guid":{"rendered":"http:\/\/www.elbeno.com\/blog\/?p=338"},"modified":"2007-07-29T12:37:59","modified_gmt":"2007-07-29T19:37:59","slug":"arboreal-haskell","status":"publish","type":"post","link":"https:\/\/www.elbeno.com\/blog\/?p=338","title":{"rendered":"Arboreal Haskell"},"content":{"rendered":"

(Chapter 7 of The Haskell School of Expression<\/em> is about trees.)<\/p>\n

The first definition is of a tree with values stored only at the leaves, i.e.<\/p>\n

data Tree a = Leaf a | Branch (Tree a) (Tree a)<\/tt><\/p>\n

It then gives a mapTree<\/tt> function (equivalent to map<\/tt> on a list), which is trivial, and functions fringe<\/tt>, treeSize<\/tt> and treeHeight<\/tt>, which return respectively the list of the leaf values, the number of leaves, and the max depth. In the text, these are defined in the usual recursive way. An exercise is to write a Tree<\/tt> equivalent of the fold<\/tt> function for lists. Which I think I managed:<\/p>\n

foldTree :: (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<\/pre>\n
The trick was in recognising that I needed two functions, one for dealing with leaves and the other for dealing with branches (because (:)<\/tt> is a different type from (++)<\/tt> and both are used in fringe<\/tt>). Of course, the performance implication of all those list appends makes me think that in the real world, I’d write fringe<\/tt> using only (:)<\/tt>:<\/p>\n
fastFringe :: Tree a -> [a]\r\nfastFringe t = acc t []\r\n    where acc (Leaf x) l = x : l\r\n          acc (Branch x y) l = acc x (acc y l)<\/pre>\n
(It also occurs to me that fringe<\/tt> is more usually called flatten<\/tt> IME). The next exercises involved trees with internal values (not at the leaves), i.e.<\/p>\n
data InternalTree a = ILeaf\r\n                    | IBranch a (InternalTree a) (InternalTree a)<\/pre>\n
This is a bit more like way I’m used to trees working, and the exercises were easier. InternalTree<\/tt> versions of zipWith<\/tt> and zip<\/tt> (defined in terms of zipWith<\/tt> of course) were easy, as were versions of take<\/tt> and takeWhile<\/tt>. I was impressed with the “magic” of the InternalTree<\/tt> version of repeat<\/tt>:<\/p>\n
repeatInternalTree :: a -> InternalTree a\r\nrepeatInternalTree a = t\r\n    where t = (IBranch a (t) (t))<\/pre>\n
There are two bits of magic here. First, this is an infinitely recursive definition. Haskell uses lazy evaluation, so this is designed to be used with takeTree<\/tt> or takeTreeWhile<\/tt>. The second piece of magic: where is the base case constructor (ILeaf<\/tt>) specified? It isn’t! Yet<\/p>\n
takeTree 2 (repeatInternalTree 5)<\/tt><\/p>\n
returns<\/p>\n
IBranch 5 (IBranch 5 ILeaf ILeaf) (IBranch 5 ILeaf ILeaf)<\/tt><\/p>\n
as hoped for, if not quite expected. The only thing I’m not really grokking right now are the InternalTree<\/tt> versions of foldr<\/tt> and possibly foldl<\/tt> (and possibly a third type of fold). I’ve got a feeling there is some higher-order function extractable that controls pre-, post-, or in-order node traversal on InternalTree<\/tt>, but I’m unsure of the structural differences of foldl<\/tt> and foldr<\/tt> when applied to trees. I am also puzzling a bit over the semantics of zipWith<\/tt> and zip<\/tt> when applied to trees with only leaf-node values.<\/p>\n
PS. Gleep = glorp.<\/p>\n","protected":false},"excerpt":{"rendered":"
(Chapter 7 of The Haskell School of Expression is about trees.) The first definition is of a tree with values stored only at the leaves, i.e. data Tree a = Leaf a | Branch (Tree a) (Tree a) It then gives a mapTree function (equivalent to map on a list),…<\/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-338","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\/338","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=338"}],"version-history":[{"count":0,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/338\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=338"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=338"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.elbeno.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=338"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}