Haskell – 129 – zippers – 1

Continuo da qui, copio qui.

While Haskell’s purity comes with a whole bunch of benefits, it makes us tackle some problems differently than we would in impure languages. Because of referential transparency, one value is as good as another in Haskell if it represents the same thing.

So if we have a tree full of fives (high-fives, maybe?) and we want to change one of them into a six, we have to have some way of knowing exactly which five in our tree we want to change. We have to know where it is in our tree. In impure languages, we could just note where in our memory the five is located and change that. But in Haskell, one five is as good as another, so we can’t discriminate based on where in our memory they are. We also can’t really change anything; when we say that we change a tree, we actually mean that we take a tree and return a new one that’s similar to the original tree, but slightly different.

One thing we can do is to remember a path from the root of the tree to the element that we want to change. We could say, take this tree, go left, go right and then left again and change the element that’s there. While this works, it can be inefficient. If we want to later change an element that’s near the element that we previously changed, we have to walk all the way from the root of the tree to our element again!

In this chapter, we’ll see how we can take some data structure and focus on a part of it in a way that makes changing its elements easy and walking around it efficient. Nice!

Like we’ve learned in biology class, there are many different kinds of trees, so let’s pick a seed that we will use to plant ours. Here it is:

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

So our tree is either empty or it’s a node that has an element and two sub-trees. Here’s a fine example of such a tree, which I give to you, the reader, for free!

freeTree :: Tree Char
freeTree =
    Node 'P'
        (Node 'O'
            (Node 'L'
                (Node 'N' Empty Empty)
                (Node 'T' Empty Empty)
            )
            (Node 'Y'
                (Node 'S' Empty Empty)
                (Node 'A' Empty Empty)
            )
        )
        (Node 'L'
            (Node 'W'
                (Node 'C' Empty Empty)
                (Node 'R' Empty Empty)
            )
            (Node 'A'
                (Node 'A' Empty Empty)
                (Node 'C' Empty Empty)
            )
        )

And here’s this tree represented graphically:

Notice that W in the tree there? Say we want to change it into a P. How would we go about doing that? Well, one way would be to pattern match on our tree until we find the element that’s located by first going right and then left and changing said element. Here’s the code for this:

changeToP :: Tree Char -> Tree Char
changeToP (Node x l (Node y (Node _ m n) r)) = Node x l (Node y (Node 'P' m n) r)

Yuck! Not only is this rather ugly, it’s also kind of confusing. What happens here? Well, we pattern match on our tree and name its root element x (that’s becomes the 'P' in the root) and its left sub-tree l. Instead of giving a name to its right sub-tree, we further pattern match on it. We continue this pattern matching until we reach the sub-tree whose root is our 'W'. Once we’ve done this, we rebuild the tree, only the sub-tree that contained the 'W' at its root now has a 'P'.

Is there a better way of doing this? How about we make our function take a tree along with a list of directions. The directions will be either L or R, representing left and right respectively, and we’ll change the element that we arrive at if we follow the supplied directions. Here it is:

data Direction = L | R deriving (Show)
type Directions = [Direction]

changeToP :: Directions-> Tree Char -> Tree Char
changeToP (L:ds) (Node x l r) = Node x (changeToP ds l) r
changeToP (R:ds) (Node x l r) = Node x l (changeToP ds r)
changeToP [] (Node _ l r) = Node 'P' l r

If the first element in the our list of directions is L, we construct a new tree that’s like the old tree, only its left sub-tree has an element changed to 'P'. When we recursively call changeToP, we give it only the tail of the list of directions, because we already took a left. We do the same thing in the case of an R. If the list of directions is empty, that means that we’re at our destination, so we return a tree that’s like the one supplied, only it has 'P' as its root element.

To avoid printing out the whole tree, let’s make a function that takes a list of directions and tells us what the element at the destination is:

elemAt :: Directions -> Tree a -> a
elemAt (L:ds) (Node _ l _) = elemAt ds l
elemAt (R:ds) (Node _ _ r) = elemAt ds r
elemAt [] (Node x _ _) = x

This function is actually quite similar to changeToP, only instead of remembering stuff along the way and reconstructing the tree, it ignores everything except its destination. Here we change the 'W' to a 'P' and see if the change in our new tree sticks (raccolgo in z0.hs):

Prelude> :l z0
[1 of 1] Compiling Main             ( z0.hs, interpreted )
Ok, modules loaded: Main.
*Main> let newTree = changeToP [R,L] freeTree
*Main> elemAt [R,L] newTree
'P'

Nice, this seems to work. In these functions, the list of directions acts as a sort of focus, because it pinpoints one exact sub-tree from our tree. A direction list of [R] focuses on the sub-tree that’s right of the root, for example. An empty direction list focuses on the main tree itself.

While this technique may seem cool, it can be rather inefficient, especially if we want to repeatedly change elements. Say we have a really huge tree and a long direction list that points to some element all the way at the bottom of the tree. We use the direction list to take a walk along the tree and change an element at the bottom. If we want to change another element that’s close to the element that we’ve just changed, we have to start from the root of the tree and walk all the way to the bottom again! What a drag.

In the next section, we’ll find a better way of focusing on a sub-tree, one that allows us to efficiently switch focus to sub-trees that are nearby.

👽

Posta un commento o usa questo indirizzo per il trackback.

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: