[Haskell-beginners] Re: [Haskell-begin] Looking for cunning ways to update a tree

[Tillmann Rendel]

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