Zipper_Haskell Notes 13

I. Immutable Data Structures

Data structures are immutable, so the result of add, delete, modify operations on them can only be to create a new copy of the data structure, for example:

reverse' xs
  | length xs <= 1 = xs
  | otherwise = last xs : (reverse' (init xs))

Reversing a List is like reversing a stack of poker cards, drawing the bottom card and placing it on top of the new stack, then drawing the second-to-last card and placing it below... So, the result of reversing the card stack is actually creating a new card stack. The new stack is still composed of the previous cards, but has no connection with the original stack, similar to state discarding, directly discard the original stack, rather than maintaining modifications, for example (general method for implementing array reversal, described in JS):

function swap(arr, from, to) {
  let t = arr[from];
  arr[from] = arr[to];
  arr[to] = t;
}
function reverse(arr) {
  for (let i = 0; i < arr.length / 2; i++) {
    swap(arr, i, arr.length - 1 - i);
  }
  return arr;
}

If data structures are mutable, array reversal can be achieved through n/2 element swaps. The difference between the two is that in mutable data structures, we treat data structures as expandable and reusable containers, operations on data structures are add, delete, modify operations on values in the container; in immutable data structures, we treat data structures as data constants, cannot expand and reuse, so operations on data structures are equivalent to creating a new copy that is very similar but not quite the same. For example swap:

swap _ _ [] = []
swap i j xs
  | i == j = xs
  | i > j = swap j i xs
  | otherwise  = (take i xs) ++ [xs !! j] ++ (sublist (i + 1) (j - 1) xs) ++ [xs !! i] ++ (drop (j + 1) xs)
  where sublist _ _ [] = []
        sublist a b xs
          | a > b = []
          | a == b = [xs !! a]
          | otherwise = (drop a . take (b + 1)) xs

A line is divided into 3 segments by 2 points, the result of swapping two elements in a List is the first segment concatenated with the second point, concatenated with the middle segment, then concatenated with the first point and the last segment

(Extracted from A Baptism of Functional Thinking Patterns)

Corresponding JS description is as follows (only key parts):

function swap(i, j, xs) {
  return xs.slice(0, i).concat([xs[j]]).concat(xs.slice(i + 1, j)).concat([xs[i]]).concat(xs.slice(j + 1));
}

Quite troublesome, and efficiency is not high, for example in tree structure scenarios, changing one node requires building a new tree, then changing its adjacent node requires creating another new tree... Simply adding +1 to all node values requires creating n complete trees. Actually, local modifications don't need to recreate the entire tree, it's more reasonable to create until a complete tree is needed. In the case of immutable data structures, can this be achieved?

II. Traversing in Data Structures

Tree

First create a binary search tree:

> let tree = fromList [7, 3, 1, 2, 6, 9, 8, 5]
> tree
Node 5 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 3 EmptyTree EmptyTree)) (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))

(fromList and binary search tree implementation from [Monoid_Haskell Notes 9](/articles/monoid-haskell 笔记 9/#articleHeader12))

Tree structure is as follows:

To modify a specified node, need to know two things: position index and new value. Position index can be represented by access path, for example:

data Direction = L | R
type Path = [Direction]

Then modify function's type should be like this:

modify :: Tree a -> Path -> Tree a -> Tree a

Find target node according to position index, replace with new value, implement like this:

modify EmptyTree _ n = n
modify t [] n = n
modify (Node x l r) (d:ds) n
  | d == L = Node x (modify l ds n) r
  | d == R = Node x l (modify r ds n)

Try it out, change 3 to 4, access path is [L, R]:

> modify tree [L, R] (singleton 4)
Node 5 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))

Meets expectations, if want to change 1 after changing 3?

Can use the complete tree after changing 3 as input, then start from root node to find 1 and change to 0:

> modify (modify tree [L, R] (singleton 4)) [L, L] (singleton 0)
Node 5 (Node 2 (Node 0 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))

Usable, but exists 2 problems:

Complete tree generated after changing 3 is redundant
1 is 3's left sibling, no need to search from root again

Actually, what we hope is:

Don't generate intermediate redundant complete trees, generate complete tree only when needed (such as after a series of modification operations)
Can conveniently perform local modifications (change left/right siblings, parent/children), without worrying about complete tree

To perform multiple modifications on a subtree, and still be able to generate complete tree after modifications, how to achieve?

Need to retain structural context information while performing local modifications. For example when modifying right subtree, focus is:

For binary trees, structural context information consists of two parts, parent node and sibling nodes:

-- Parent node
5
-- Left sibling
2
  1
  3

Right subtree plus these two parts of information, can get complete subtree with parent node as root. Similarly, if parent node also has its parent node and sibling node information, can continue upward to restore subtree, when reaching root can get complete tree. Actually, as long as having enough structural context information, can traverse up/down/left/right arbitrarily in tree, and can stop at any time to rebuild complete tree

First define structural context information:

data DirectionWithContext a = LeftSibling a (Tree a) | RightSibling a (Tree a) deriving (Show, Eq)
type PathWithContext a = [DirectionWithContext a]
type TreeWithContext a = (Tree a, PathWithContext a)

Use LeftSibling a (Tree a) to record structural context information, where a represents parent node's value, Tree a represents right sibling, this is minimum information needed to restore subtree upward, not a bit redundant. PathWithContext is similar to previous Path, also used to represent access path, just each step of path besides recording direction, also records corresponding context information, including parent node and sibling nodes

Then implement "arbitrary traversal":

goLeft ((Node x l r), ps) = (l, ((LeftSibling x r) : ps))
goRight ((Node x l r), ps) = (r, ((RightSibling x l) : ps))
goUp (l, ((LeftSibling x r):ps)) = (Node x l r, ps)
goUp (r, ((RightSibling x l):ps)) = (Node x l r, ps)

Walk two steps to try, still walk previous scenario, first find 3, then find 1, that is first go left then right, then go up, finally go left:

> let cTree = (tree, [])
> let focus = goLeft (goUp (goRight (goLeft cTree)))
> fst focus
Node 1 EmptyTree EmptyTree
> snd focus
[LeftSibling 2 (Node 3 EmptyTree EmptyTree),LeftSibling 5 (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))]

Found subtree where 1 is located, and retains complete access path (5's left sibling 2's left sibling)

To rebuild complete tree, just need to walk back to tree root along original path, do like this:

backToRoot (t, []) = (t, [])
backToRoot t = backToRoot $ goUp t

Verify:

> fst $ backToRoot focus
Node 5 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 3 EmptyTree EmptyTree)) (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))

After being able to traverse freely, and rebuild complete tree at any time, modify becomes very simple:

modifyTreeWithContext (EmptyTree, ps) _ = (EmptyTree, ps)
modifyTreeWithContext ((Node x l r), ps) v = ((Node v l r), ps)

Do it again, first change 3 to 4, then change 1 to 0:

> let modified = modifyTreeWithContext (goLeft (goUp (modifyTreeWithContext (goRight (goLeft cTree)) 4))) 0
> fst modified
Node 0 EmptyTree EmptyTree
> fst $ backToRoot modified
Node 5 (Node 2 (Node 0 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))

Consistent with previous result. Looks not very clear, use utility functions:

x +> f = f x
m = flip modifyTreeWithContext

Simple transformation, to describe in more natural way:

> fst $ backToRoot $ cTree +> goLeft +> goRight +> m 4 +> goUp +> goLeft +> m 0
Node 5 (Node 2 (Node 0 EmptyTree EmptyTree) (Node 4 EmptyTree EmptyTree)) (Node 8 (Node 6 EmptyTree (Node 7 EmptyTree EmptyTree)) (Node 9 EmptyTree EmptyTree))

Start from tree root, go left, go right, change to 4, then go up, go left, change to 0, a series of operations quite natural, didn't feel limitations of immutable data structures

List

Actually, List can also be operated in this more natural way, just need to bring structural context information

For List, only left and right 2 directions, much simpler than tree scenario:

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

Left/right traversal, rebuild complete List, modify elements all easy to implement:

goListRight (x:xs, ps) = (xs, x:ps)
goListLeft (xs, p:ps) = (p:xs, ps)
backToHead (xs, []) = (xs, [])
backToHead ls = backToHead $ goListLeft ls
modifyListWithContext ([], ps) _ = ([], ps)
modifyListWithContext (x:xs, ps) v = (v:xs, ps)

Try it out:

> let list = [1, 3, 5, 7, 8, 10, 12]
> let cList = (list, [])
> m = flip modifyListWithContext
> let modified = cList +> goListRight +> goListRight +> goListRight +> m 4 +> goListLeft +> goListLeft +> m 2
> modified
([2,5,4,8,10,12],[1])
> fst $ backToHead modified
[1,2,5,4,8,10,12]

Changed 4th element to 4, 2nd element changed to 2. Compare with previous approach:

modifyList xs i x = take i xs ++ [x] ++ drop (i + 1) xs
> modifyList (modifyList list 1 2) 3 4
[1,2,5,4,8,10,12]

Difference between the two is that the former supports traversing and modifying elements in an intuitive way, no perception of immutable limitations

III. What is Zipper

TreeWithContext, ListWithContext we defined above are all Zipper, formal description is as follows:

The Zipper is an idiom that uses the idea of "context" to the means of manipulating locations in a data structure.

Use "context" idea to handle positions in data structures, habitual name is Zipper. Why called "Zipper"?

ListWithContext is zipper, very vivid. Treat List as zipper, lock head is a cursor (or understand as pointer), element at position cursor points to is current element, remaining elements are its context. Lock head pulled right, held left (imagine pulling file bag seal action), corresponding to data structure operations is, access new elements to right, pulling to rightmost is traversal, access historical elements to left, pulling to leftmost is rebuilding complete List

Similarly, TreeWithContext can also be understood this way, pull left and right, access new elements, pull up, access historical elements, pulling to top is rebuilding complete tree

Specifically, Zipper can be divided according to its generality:

Zipper for specific data structures: such as ListZipper, TravelTree, TravelBTree
Generic Zipper: such as Zipper Monad, Generic Zipper

We have already implemented two Zippers for specific data structures (just change xxxWithContext to Zipper), general idea is:

Zipper, the functional cursor into a data structure, is itself a data structure, derived from the original one. The derived data type D' for the recursive data type D is D with exactly one hole. Filling-in the hole -- integrating over all positions of the hole -- gives the data type D back.

Derive Zipper structure from given data structure, specific approach is to split original data structure into two parts, substructure (as value) and structure with "hole" (as value's structural context, has "hole" because substructure where value is located was dug out from original complete structure), these two put together happen to be original complete structure, as shown in figure:

[caption id="attachment_1762" align="alignnone" width="620"] zipper-hole[/caption]

Zipper Monad

The Zipper Monad is a generic monad for navigating around arbitrary data structures. It supports movement, mutation and classification of nodes (is this node the top node or a child node?, etc).

Besides supporting movement, modification, can also distinguish node types. Basic implementation is as follows:

import Control.Monad.State

data Loc c a = Loc { struct :: a,
                    cxt    :: c }
            deriving (Show, Eq)

newtype Travel loc a = Travel { unT :: State loc a }
    deriving (Functor, Monad, MonadState loc, Eq)

Structure + Context = Location, traverse and modify through several monadic functions:

traverse :: Loc c a            -- starting location (initial state)
        -> Travel (Loc c a) a -- locational computation to use
        -> a                  -- resulting substructure
traverse start tt = evalState (unT tt) start

-- modify the substructure at the current node
modifyStruct :: (a -> a) -> Travel (Loc c a) a
modifyStruct f = modify editStruct >> liftM struct get where
    editStruct (Loc s c) = Loc (f s) c

-- put a new substructure at the current node
putStruct :: a -> Travel (Loc c a) a
putStruct t = modifyStruct $ const t

-- get the current substructure
getStruct :: Travel (Loc c a) a
getStruct = modifyStruct id -- works because modifyTree returns the 'new' tree

P.S. Originally designed as generic Monad for Zipper, but found not needed:

It's designed for use with The Zipper but in fact there is no requirement to use such an idiom.

Currently seems to be treated as tree structure specific:

Zipper monad is a monad which implements the zipper for binary trees.

Generic Zipper

Another generic Zipper:

Generic Zipper: the context of a traversal

Treat Zipper as traversal operation's context, different from previous idea:

We advocate a different view, emphasizing not the result of navigating through a data structure to a desired item and extracting it, but the process of navigation.

Don't emphasize moving to some position in data structure, accessing wanted things, but only focus on the process of movement:

Each data structure comes with a method to enumerate its components, representing the data structure as a stream of the nodes visited during the enumeration. To let the user focus on a item and submit an update, the enumeration process should yield control to the user once it reached an item.

From traversal perspective, data structure is stream of nodes visited during enumeration process. Then, to focus on some node and update, enumeration process should yield control back to user when reaching that node, for example:

Current element: 1
Enter Return, q or the replacement value:

Current element: 2
Enter Return, q or the replacement value:

Current element: 6
Enter Return, q or the replacement value:
42
Current element: 24
Enter Return, q or the replacement value:
q
Done:
fromList [(1,1),(2,2),(3,42),(4,24),(5,120),(6,720),(7,5040),(8,40320),(9,362880),(10,3628800)]

(Specifically see ZipperTraversable)

P.S. This idea is very similar to [generators in JS](/articles/javascript 生成器/#articleHeader8), take a breath after every step to see whether to modify elements, or stop traversal:

As Chung-chieh Shan aptly put it, 'zipper is a suspended walk.'