Haskell – 131 – zippers – 3

Continuo da qui, copio qui.

Focalizzare con le liste
Zippers can be used with pretty much any data structure, so it’s no surprise that they can be used to focus on sub-lists of lists. After all, lists are pretty much like trees, only where a node in a tree has an element (or not) and several sub-trees, a node in a list has an element and only a single sub-list. When we implemented our own lists [qui], we defined our data type like so:

data List a = Empty | Cons a (List a) deriving (Show, Read, Eq, Ord)

Contrast this with our definition of our binary tree and it’s easy to see how lists can be viewed as trees where each node has only one sub-tree.

A list like [1,2,3] can be written as 1:2:3:[]. It consists of the head of the list, which is 1 and then the list’s tail, which is 2:3:[]. In turn, 2:3:[] also has a head, which is 2 and a tail, which is 3:[]. With 3:[], the 3 is the head and the tail is the empty list [].

Let’s make a zipper for lists. To change the focus on sub-lists of a list, we move either forward or back (whereas with trees we moved either up or left or right). The focused part will be a sub-tree and along with that we’ll leave breadcrumbs as we move forward. Now what would a single breadcrumb for a list consist of? When we were dealing with binary trees, we said that a breadcrumb has to hold the element in the root of the parent node along with all the sub-trees that we didn’t choose. It also had to remember if we went left or right. So, it had to have all the information that a node has except for the sub-tree that we chose to focus on.

Lists are simpler than trees, so we don’t have to remember if we went left or right, because there’s only one way to go deeper into a list. Because there’s only one sub-tree to each node, we don’t have to remember the paths that we didn’t take either. It seems that all we have to remember is the previous element. If we have a list like [3,4,5] and we know that the previous element was 2, we can go back by just putting that element at the head of our list, getting [2,3,4,5].

Because a single breadcrumb here is just the element, we don’t really have to put it inside a data type, like we did when we made the Crumb data type for tree zippers:

type ListZipper a = ([a],[a])

The first list represents the list that we’re focusing on and the second list is the list of breadcrumbs. Let’s make functions that go forward and back into lists:

goForward :: ListZipper a -> ListZipper a
goForward (x:xs, bs) = (xs, x:bs)

goBack :: ListZipper a -> ListZipper a
goBack (xs, b:bs) = (b:xs, bs)

When we’re going forward, we focus on the tail of the current list and leave the head element as a breadcrumb. When we’re moving backwards, we take the latest breadcrumb and put it at the beginning of the list.

Raccolgo il codice nel file zl0.hs.

Here are these two functions in action:

Prelude> :l zl0
[1 of 1] Compiling Main             ( zl0.hs, interpreted )
Ok, modules loaded: Main.
*Main> let xs = [1,2,3,4]
*Main> goForward (xs,[])
*Main> goForward ([2,3,4],[1])
*Main> goForward ([3,4],[2,1])
*Main> goBack ([4],[3,2,1])

We see that the breadcrumbs in the case of lists are nothing more but a reversed part of our list. The element that we move away from always goes into the head of the breadcrumbs, so it’s easy to move back by just taking that element from the head of the breadcrumbs and making it the head of our focus.

This also makes it easier to see why we call this a zipper, because this really looks like the slider of a zipper moving up and down.

If you were making a text editor, you could use a list of strings to represent the lines of text that are currently opened and you could then use a zipper so that you know which line the cursor is currently focused on. By using a zipper, it would also make it easier to insert new lines anywhere in the text or delete existing ones.

Pausa 😜


Posta un commento o usa questo indirizzo per il trackback.



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: