Hi Matt, Quergle Quergle wrote:
I have the following bit of code that updates a tree structure given a route to a leaf:
data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show, Eq) data PathSelector = GoLeft | GoRight deriving (Show, Eq) type Path = [PathSelector]
selectChild (Node left _) GoLeft = left selectChild (Node _ right ) GoRight = right
updateNode (Node _ right) GoLeft newLeft = Node newLeft right updateNode (Node left _) GoRight newRight = Node left newRight
updateLeaf new (Leaf previous) = Leaf new
updateTree :: Tree a -> Path -> a -> Tree a updateTree tree path newValue = case path of [] -> updateLeaf newValue tree (p:ps) -> updateNode tree p (updateTree' (selectChild tree p) ps newValue)
I wanted to rewrite updateTree without using explicit recursion. Unfortunately, the best I could come up with is:
upDownRecurse :: (a -> b -> a) -> (a -> c) -> (a -> b -> c -> c) -> a -> [b] -> c upDownRecurse down bottoming up = upDownRecurse' where upDownRecurse' acc [] = bottoming acc upDownRecurse' acc (x:xs) = up acc x (upDownRecurse' (down acc x) xs)
updateTree' :: Tree a -> Path -> a -> Tree a updateTree' tree path newValue = upDownRecurse selectChild (updateLeaf newValue) updateNode tree path
So what's the sexier way of doing this?
I would approach that problem sligthly differently, by writing combinators for tree updaters. A combinator is a function which works on function and produces new functions, like (.), which composes two functions. Combinators can be very helpful to produce complex functions out of simple ones. A tree updater is a function of type (Tree a -> Tree a). A simple tree updater works only on Leafs, and sets the value stored in the leaf: onLeaf :: a -> Tree a -> Tree a onLeaf new (Leaf previous) = Leaf new onLeaf new (Node left right) = error "not a leaf" Note that the type of onLeaf can be read as (a -> (Tree a -> Tree a)), emphasizing that it takes a new value, and returns a tree updater. Given such a tree updater and Tree, we can do the following things: (1) apply the updater to the tree (2) apply the updater to the left subtree, leave the right unchanged (3) apply the updater to the right subtree, leave the left unchanged Case (1) is just function application, but for (2) and (3) we can define the following combinators: onLeft :: (Tree a -> Tree a) -> Tree a -> Tree a onLeft updater (Leaf x) = error "not a node" onLeft updater (Node a b) = Node (updater a) b onRight :: (Tree a -> Tree a) -> Tree a -> Tree a onRight updater (Leaf x) = error "not a node" onRight updater (Node a b) = Node a (updater b) Note that the types of onLeft and onRight can be read (Tree a -> Tree a) -> (Tree a -> Tree a), emphasizing their function as "tree updater transformer". They take a tree updater, and return a different tree updater. Now, we want to transform a call to updateTree such as updateTree tree [GoLeft, GoLeft, GoRight] 42 into onLeft (onLeft (onRight (onLeaf 42))). As a first step, note that the nested tree updater above can be written as onLeft . onLeft . onRight . onLeaf $ 42 using the (.) and ($) combinators. Try to implement onPath :: Path -> (Tree a -> Tree a) -> Tree a -> Tree a and updateTree in terms of onPath and onLeaf. (onPath path updater) is supposed to apply updater to the subtree denoted by path. You can also try to write some more combinators, like onNode :: (Tree a -> Tree a) -> (Tree a -> Tree a) -> Tree a -> Tree a applyLeaf :: (a -> a) -> Tree a -> Tree a onTree :: (Tree a -> Tree a) -> (Tree a -> Tree a) -> Tree a -> Tree a everywhere :: (Tree a -> Tree a) -> Tree a -> Tree a (onNode f g) works for Nodes, and applies f to the left, and g to the right subtree. (applyLeaf f) works for Leafs, and applies f to the value stored in the leaf. (onTree f g) works for Leafs and Nodes, and applies f to the tree if it is a Leaf, and g if it is a Node. (everywhere f) works for whole trees, and applies f to each subtree, and each subtree of each subtree, and so on. It is possible to write onLeaf, onLeft and onRight in terms of these more general combinators. What is the minimum choice of combinators you need to define with pattern matching on Tree, so that all other combinators can be defined using only other combinators? Tillmann