## 一.不可变的数据结构

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

```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;
}```

```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```

（摘自一场函数式思维模式的洗礼）

```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));
}```

## 二.在数据结构中穿梭

### 树

```> 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`及二叉搜索树的实现来自Monoid_Haskell笔记9）

```5
2
1
3
8
6
空
7
9```

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

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

```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)```

```> 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))```

```> 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))```

• 改完`3`之后生成的完整树是多余的
• `1`就是`3`的左兄弟，不需要再从根开始找

• 不生成中间多余的完整树，在需要的时候（比如一系列修改操作之后）才生成完整树
• 能够方便地进行局部修改（改左右兄弟、父级子级），而不用关注完整树

```8
6
空
7
9```

```-- 父节点
5
-- 左兄弟
2
1
3```

```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)```

`LeftSibling a (Tree a)`来记录结构上下文信息，其中`a`表示父节点的值，`Tree a`表示右兄弟，这是向上恢复子树所需的最小信息，一点不多余。`PathWithContext`与之前的`Path`类似，同样用来表示访问路径，只是路径的每一步除了记录方向，还记录了相应的上下文信息，包括父节点和兄弟节点

```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)```

```> 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))]```

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

```> 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))```

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

```> 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))```

```x +> f = f x
m = flip modifyTreeWithContext```

```> 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))```

### List

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

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

```> 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])
[1,2,5,4,8,10,12]```

```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]```

## 三.Zipper是什么东西

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

`ListWithContext`就是拉链，非常形象。把List当作拉链，锁头是一个游标（cursor，或者理解成指针），游标所指的位置上的元素就是当前元素，其余元素是其上下文。锁头向右拉开，向左拉住（想象拉文件袋封口的动作），对应到数据结构操作中就是，向右访问新元素，拉到最右端就是遍历，向左访问历史元素，拉到最左端就是重建完整List

• 针对特定数据结构的Zipper：如ListZipper、TravelTree、TravelBTree

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.

zipper-hole

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).

```import Control.Monad.Statedata Loc c a = Loc { struct :: a,
cxt    :: c }
deriving (Show, Eq)newtype Travel loc a = Travel { unT :: State loc a }

`结构 + 上下文 = 位置`，通过几个monadic函数来遍历、修改：

```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```

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

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

### Generic Zipper

Generic Zipper: the context of a traversal

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.

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.

```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)]```

（具体见ZipperTraversable）

P.S.这个思路像极了JS里的生成器，每走一步都喘口气看看要不要修改元素，或者停止遍历：

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

### 参考资料

• Zipper
• Control.Zipper
• Haskell error: Couldn’t match type ‘a’ with ‘b’

0 条评论

### 相关文章

数学世界里，0是加法单位元，1是乘法单位元（identity element），例如：

• ### 接口_TypeScript笔记3

对于对象等复杂结构的类型，TypeScript的理念是鸭子类型（duck typing），即值的“形状”：

• ### 一场函数式思维模式的洗礼

按照习惯的命令式思维，遍历List计数搞定。那么，如何用递归描述List的长度（即提供其递归定义）？

• ### MySQL - CASE WHEN的高级用法

注意事项：一定要有WHERE id IN的限制，否则不在WHEN中的记录就会被置为NULL

• ### 适配器模式与SpringMVC

适配器模式是将一个接口转换成客户希望的另一个接口，使接口不兼容的那些类可以一起工作，其别名为包装器(Wrapper)。适配器模式既可以作为类结构型模式，也可以作...

• ### 小白博客 最简单开启3389端口方法

当我们拿到管理员账号密码的时候，我们需要利用3389端口远程桌面连接到对方服务器，发现3389端口没有开放，此时需要我们远程开启目标服务器3389端口。 ...

• ### vi编辑器

vim是linux上使用最多的编辑器，熟悉这个编辑器的使用，可以大大提高我们的工作效率。

• ### Swift：轻量级API的设计（一）

Swift的最强大功能之一就是在设计API方面给我们提供了极大的灵活性。这种灵活性不仅使我们能够定义易于理解和使用的函数和类型，还使我们能够创建给人以非常轻量级...

• ### 资源池模式和单例模式实现的自定义数据库连接池java实现版

在企业级开发中，我们往往不会直接使用原生的JDBC操作来实现与数据库得连接。因为数据库的连接是一个很宝贵的资源且耗时，我们往往会在内存中引入一个资源池来统一管理...