Hey Matt, On 24 jul 2008, at 20:29, Quergle Quergle wrote:
Hello all,
This is a really helpful list: I've learned half a dozen new things just by reading this month's traffic. Anyway...I have the following bit of code that updates a tree structure given a route to a leaf:
[...]
I wanted to rewrite updateTree without using explicit recursion. Unfortunately, the best I could come up with is:
[...]
So what's the sexier way of doing this?
The trick here is to define a fold for a tree. A fold is a function that does all the recursion, and you can then define other functions in terms of that fold. The type of the fold function is based on the structure of your data. So, for the fold of the tree, you basically first have to take two functions:
leaf :: a -> r node :: r -> r -> r
The leaf function will act on Leaf's, and take a value of type a and turn it into a result. The node function will first compute the result for the recursive parts (so this is where the recursion happens), and then needs to combine those results. The full type of our function foldTree looks like this:
foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r
And the implementation looks like this:
foldTree leaf node (Leaf a) = leaf a foldTree leaf node (Node a b) = node (foldTree leaf node a) (foldTree leaf node b)
Now, to find a value in the tree using your Path type, we want the following type:
findTree :: Tree a -> Path -> a
So suppose we give our foldTree two arguments to handle both the Node and the Leaf, we will end up with a function that has type:
Tree a -> r
Now, what will we choose for r? Of course, it has to be Path a -> a! We now need a function (a -> Path a -> a) and a function (Path a -> a) -> (Path a -> a) -> (Path a -> a). When we remove unnecessary parentheses, the type is (Path a -> a) -> (Path a -> a) -> Path a -> a The first one is easy, we just ignore the second argument:
findLeaf a _ = a
The second one takes three arguments: the left value, the right value and the path. Based on the path we need to choose wheter to choose the left or the right value:
findNode left right (p:ps) = case p of GoLeft -> left ps GoRight -> right ps
Now we can take these parts and compose them into the findTree function:
findTree t p = foldTree findLeaf findNode t p
And because Haskell will save us from unnecessary typing, we could also write it shorter:
findTree = foldTree const findNode
Note that we didn't use any recursion in our findTree! It would be cool if you could try to come up with a definition of updateTree in terms of foldTree. Have fun, -chris P.S.: Here's the full code:
foldTree :: (a -> r) -> (r -> r -> r) -> Tree a -> r foldTree leaf node (Leaf a) = leaf a foldTree leaf node (Node a b) = node (rec a) (rec b) where rec = foldTree leaf node
findTree :: Tree a -> Path -> a findTree = foldTree const findNode where findNode left right (p:ps) = case p of GoLeft -> left ps GoRight -> right ps