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' y'
where x' = foldTree fLeaf fBranch init x
y' = foldTree fLeaf fBranch init y
fringe :: Tree a -> [a]
fringe t = foldTree (:) (++) [] t
treeSize :: Tree a -> Int
treeSize t = foldTree (\x y -> 1 + y) (+) 0 t
treeHeight :: Tree a -> Int
treeHeight t = foldTree (\x y -> 0) (\x y -> 1 + max x y) 0 t |

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' y'
where x' = foldTree fLeaf fBranch init x
y' = foldTree fLeaf fBranch init y
fringe :: Tree a -> [a]
fringe t = foldTree (:) (++) [] t
treeSize :: Tree a -> Int
treeSize t = foldTree (\x y -> 1 + y) (+) 0 t
treeHeight :: Tree a -> Int
treeHeight t = foldTree (\x y -> 0) (\x y -> 1 + max x y) 0 t

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.

This entry was posted on Saturday, July 28th, 2007 at 9:37 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.

Following also seems to work:

foldTree _ init (Leaf x) = init x

foldTree op init (Branch t1 t2) = (foldTree op init t1) `op` (foldTree op init t2)

fringe’ = foldTree (++) (:[])

treeSize’= foldTree (+) (const 1)

treeHeight’= foldTree (\x y->max x y+1) (const 0)

Yes, I also think that there is no need for an “init” value.

You only need a leaf function.

My solution is like Wieslav’s but for beginners ðŸ™‚

foldt fl fb (Leaf x) = fl x

foldt fl fb (Branch t1 t2) = fb t1′ t2′

where

t1′ = foldt fl fb t1

t2′ = foldt fl fb t2

fringe t = foldt tolist (++) t where tolist x = [x]

treeSize t = foldt one (+) t where one x = 1

treeHeight t = foldt zero max1 t

where

zero x = 0

max1 t1 t2 = 1 + max t1 t2