[Haskell-begin] Looking for cunning ways to update a tree
Chris Eidhof
chris at eidhof.nl
Thu Jul 24 19:44:01 EDT 2008
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
More information about the Beginners
mailing list