Zipperとは

Zipperというデータ構造について、図を使ってわかりやすく解説したいと思います。

この記事ではZipperがどういったものかは説明しますが、それがどう応用されうるかは紹介しません。

応用例については、少し長いですが以下の記事がわかりやすかったです。

[Haskell/Zippers - Wikibooks](https://ja.wikibooks.org/wiki/Haskell/Zippers)

また、ComonadとしてのZipperの応用例は、以下の記事がとてもわかりやすかったです。

[コモナドを使った抽象化の威力をライフゲームで試してみた - Qiita](https://qiita.com/lotz/items/fbc4788b8ea8313cbf76)

ただ、Haskellは遅延評価で、PureScriptは正格評価なので、この記事とは実装がところどころ異なります。

サンプルコードはPureScriptですが読めなくても図さえ見れば理解に大きな支障はないと思います。

これは余談ですが、シンタックスハイライトの関係で\`\`\`haskell ... \`\`\`でコードブロック書いてるの悲しさがありますね。

# Zipperとは

Zipperは、簡単に言うと「**注目している位置**」をもったデータ構造です。

今回はListのZipperについて考えます（実はList以外にもTreeのZipperなどが考えられます）。

![zipper.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/0fa83a6c-fa26-185d-9205-dd87724404f0.png)

図のように、ZipperはListの**ある要素に注目した**データ構造です。

上の図では、`Zipper a`は「**`List a`の要素`c`に注目したもの**」になっています。

イメージとしては、左右に**スタック**をもっていて、それぞれに「**注目している要素より左の要素**」、「**注目している要素より右の要素**」が**積まれている**、という感じです。

以下はPureScriptでの実装です。

```haskell
data Zipper a = Zipper (List a) a (List a)
```

ここで注意ですが、Zipperの中身のListは

```haskell
Zipper [a, b] c [d,  e]
```

ではなく、

```haskell
Zipper [b, a] c [d, e]
```

となります。

※PureScriptでは`[]`はListではなくArrayですが、わかりやすさのためListを`[]`で表現しています

これは先ほど言ったとおり、左右のListをそれぞれ「注目している要素より左の要素」「注目している要素より右の要素」の**スタックとして扱っている**ためです。

さらに、Zipperには**注目している位置を変える操作**として`left`と`right`が存在します。

![zipper-leftright.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/33aa94b4-6cf1-49f5-e4c8-b8e74cc126cf.png)

`left`は1つ左の要素に、`right`は1つ右の要素に注目します。

PureScriptでの実装は以下です。

```haskell
left :: forall a. Zipper a -> Maybe (Zipper a)
left (Zipper Nil _ _) = Nothing
left (Zipper (l:ls) c rs) = Just (Zipper ls l (c:rs))

right :: forall a. Zipper a -> Maybe (Zipper a)
right (Zipper _ _ Nil) = Nothing
right (Zipper ls c (r:rs)) = Just (Zipper (c:ls) r rs)
```

`left`、`right`はそれぞれ左端、右端まできたときそれ以上移動できず失敗するので、Maybeで表現しています。

# ZipperはComonad

実はZipperは**Comonad**になります。

Comonadの正体についてはとても抽象的で説明できる自信がないので、この記事では説明しません。

Zipperという具体例を通してなんらかの理解が得られればと思います。

Comonadになるためには、**以下の関数を実装する必要**があります。

```haskell
extract :: Comonad w => w a -> a
duplicate :: Comonad w => w a -> w (w a)
extend :: Comonad w => (w a -> b) -> w a -> w b
```

[Control.Comonad - purescript-control - Pursuit](https://pursuit.purescript.org/packages/purescript-control/4.2.0/docs/Control.Comonad)

今はまだ全然読めなくても大丈夫です。

実は、後ほどわかりますが

```haskell
duplicate = extend identity
extend f = map f <<< duplicate
```

となるので、`duplicate`と`extend`は**どちらか片方だけ実装すれば十分**です。

では、順に説明していきます。

## ZipperはFunctor

Comonadであるためには、まず**Functor**である必要があります。

Functorであるためには、**関数`map`を実装している必要**があります。

```haskell
map :: forall a b f. Functor f => (a -> b) -> f a -> f b
```

Zipperでは以下のようになります。

![zipper-map.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/fcd313b9-3211-c24d-1a20-1743ad47ed86.png)

Zipperの`map f`は、Listと同じように、中身の要素すべてに`f`を適用するだけです。

PureScriptでの実装は以下です。

```haskell
map :: forall a b. (a -> b) -> Zipper a -> Zipper b
map f (Zipper ls c rs) = Zipper (map f ls) (f c) (map f rs)
```

## extract

`extract`は、「**注目している要素を取り出す**」操作です。

![zipper-extract.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/9b300c18-bb83-7aef-2f75-a5cd1258b2ec.png)

Zipperは要素の1つに注目しているのですから、その**注目している要素を取り出したくなる**のは自然ですね。

```haskell
extract :: forall a. Zipper a -> a
extract (Zipper ls c rs) = c
```

## duplicate

`extend`は少し複雑なので、先に`duplicate`から説明します。

Zipperは、**注目している要素**をもち、またその**注目している要素を移動させることができる**のでしたよね。

`duplicate`は、**それぞれの要素について注目しているZipper**をすべて集めてきて、さらに**それらのZipper**を作ります。

![zipper-duplicate.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/31b852da-e3a2-8c37-8fee-330e26d67cec.png)

`A`, `B`, `C`がそれぞれ「**`a`に注目している状態のZipper**」「**`b`に注目している状態のZipper**」「**`c`に注目している状態のZipper**」ですね。

そして、**それらを集めてまたZipperにしたもの**が`Zipper (Zipper a)`となります。

`duplicate`はイメージとしては簡単なのですが、実装は少しだけ複雑になります。

```haskell
iterateLeft :: forall a. Zipper a -> List (Zipper a)
iterateLeft z = iterateLeft' z Nil
  where
  iterateLeft' :: Zipper a -> List (Zipper a) -> List (Zipper a)
  iterateLeft' z@(Zipper Nil _ _) accum = z : accum
  iterateLeft' z@(Zipper (l:ls) c rs) accum =
    iterateLeft' (z : accum)
                 (Zipper ls l (c:rs))

iterateRight :: forall a. Zipper a -> List (Zipper a)
iterateRight z = iterateRight' z Nil
  where
  iterateRight' z@(Zipper ls c Nil) accum = z : accum
  iterateRight' z@(Zipper ls c (r:rs)) accum =
    iterateRight' (z : accum)
                  (Zipper (c:ls) r rs)

duplicate :: forall a. Zipper a -> Zipper (Zipper a)
duplicate z = Zipper (drop 1 $ iterateLeft z)
                     z
                     (drop 1 $ iterateRight z)
```

むずかしいことをしているように見えますが、やりたいことは簡単で

```haskell
iterateLeft (Zipper [b, a] c [d, e])
= [ Zipper []     a [b, c, d, e]
  , Zipper [a]    b [c, d, e]
  , Zipper [b, a] c [d, e]
  ]

iterateRight (Zipper [b, a] c [d, e])
= [ Zipper [d, c, b, a] e []
  , Zipper [c, b, a]    d [e]
  , Zipper [b, a]       c [d, e]
  ]
```

です。

※わかりやすさのため`[]`をAraryではなくListとしています

つまり、`iterateLeft`は「**現在のZipperと、1つ左に注目したZipperと、もう1つ左に注目したZipperと、...**」を集めてきて、それらをListにして返します。

`iterateRight`も同様に、「**現在のZipperと、1つ右に注目したZipperと、もう1つ右に注目したZipperと、...**」を集めたListを返します。

`duplicate`では、それらを使ってそれぞれの要素に注目したZipper全体のZipperを作っています。

`iterateLeft`と`iterateRight`を**そのまま使うと現在のZipperが被る**ので、`duplicate`の中でそれらの返り値を1つのZipperにするとき**`drop 1`で現在のZipperを落としています**。

もし`drop 1`をせず

```haskell
duplicate (Zipper [b, a] c [d, e])
= Zipper
    (iterateLeft (Zipper [b, a] c [d, e])
    (Zipper [b, a] c [d, e])
    (iterateRight (Zipper [b, a] c [d, e])
```

としてしまうと、

```haskell
Zipper [C, B, A] C [C, D, E]

A = Zipper [] a [b, c, d, e]
B = Zipper [a] b [c, d, e]
C = Zipper [b, a] c [d, e]
D = Zipper [c, b, a] d [e]
E = Zipper [d, c, b, a] e []
```

となってしまい、**`C`が3つもある**ことになります。

## extend

`extend`は**少し複雑**だと言いましたよね。

その理由は**2つの処理を一度に行っているから**です。

そしてその2つというのが、**`map`と、先ほどの`duplicate`**です。

つまり、最初に少し触れたとおり

```haskell
extend f = map f <<< duplicate
```

となります。もう少し丁寧に書くと

```haskell
extend f z = map f (duplicate z)
```

ですね。

これが本当なのかは、**型を見てみる**と良いです。

```haskell
map :: (a -> b) -> w a -> w b
duplicate :: w a -> w (w a)
extend :: (w a -> b) -> w a -> w b

f :: w a -> b
extend f :: w a -> w b

map f :: w (w a) -> w b -- map の型について a = w a と見る
map f <<< duplicate :: w a -> w b

extend f = map f <<< duplicate
```

`exten f`は`map f <<< duplicate`になりそうですね。

つまり、`extend f`は**`duplicate`してから、その各要素に`f`を適用します(`map f`)**。

![zipper-extend.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/225715/b79fa08d-bb54-f52b-80ab-027e8cba1fd2.png)


`duplicate`のときと同様に、`A`, `B`, `C`がそれぞれ「**`a`に注目している状態のZipper**」「**`b`に注目している状態のZipper**」「**`c`に注目している状態のZipper**」です。

そして`extend`は`f :: Zipper a -> b`という関数を受け取るので、最終的な出力は`Zipper b`になります。

PureScriptでの実装は以下です。

```haskell
extend :: forall a b. (Zipper a -> b) -> Zipper a -> Zipper b
extend f = map f <<< duplicate

-- または
extend f z = map f (duplicate z)
```

# まとめ

ここまでで、Zipperが**どういったデータ構造**で、また**どのようにComonadとなるのか**がわかったと思います。

今回はListのZipperがComonadになることを見ましたが、**TreeのZipper**など他のZipperを見てみたり、他のComonadを見てみると面白いかもしれませんね。

[Pursuit](https://pursuit.purescript.org/)で色々見てみると面白いかもしれません。

[Data.Tree - purescript-tree - Pursuit](https://pursuit.purescript.org/packages/purescript-tree/1.3.2/docs/Data.Tree)なんて言うのがありますが、Treeの実装に**Cofree**を使っているので、先にCofreeをやらないと少し読みづらいですね。

そのうち**CofreeでTreeをつくる**記事とか書いてみたいです。

さらっとだけ言うと、Freeは**FunctorからMonadが**作れ、Cofreeは**FunctorからComonadが**つくれます。

言ってませんでしたが、Treeはその**Zipperだけでなく、それ自体もComonad**になれます。

ちなみにCofreeと関係のあるFreeに関しては以下の記事がわかりやすかったです。

[そろそろFreeモナドに関して一言いっとくか - モナドとわたしとコモナド](http://fumieval.hatenablog.com/entry/20121111/1352614885)

[free の検索結果 - モナドとわたしとコモナド](http://fumieval.hatenablog.com/search?q=free)

この方のブログは大変わかりやすく、とてもお世話になりました。

# おまけ１：PureScriptでの実装コード全文

PureScriptでは`Comonad`をより抽象化した`Extend`が定義されています。

また、今回はわかりやすさのため`extend`を`duplicate`を使って実装しました。

ただ、PureScriptでは`duplicate`は`Control.Comonad`で

```haskell
duplicate :: forall a w. Extend w => w a -> w (w a)
duplicate = extend identity
```

と実装されているので、直接`extend`を実装しています。

詳しくは[Pursuit](https://pursuit.purescript.org/)で見てみてください。

[Control.Comonad - purescript-control - Pursuit](https://pursuit.purescript.org/packages/purescript-control/4.2.0/docs/Control.Comonad)

```haskell
module Data.List.Zipper where

import Prelude
import Control.Comonad (class Comonad)
import Control.Extend (class Extend)
import Data.List (List(..), (:), drop)
import Data.Maybe (Maybe(..))

data Zipper a = Zipper (List a) a (List a)

left :: forall a. Zipper a -> Maybe (Zipper a)
left (Zipper Nil _ _) = Nothing
left (Zipper (l:ls) c rs) = Just $ Zipper ls l (c:rs)

right :: forall a. Zipper a -> Maybe (Zipper a)
right (Zipper _ _ Nil) = Nothing
right (Zipper ls c (r:rs)) = Just $ Zipper (c:ls) r rs

instance functorZipper :: Functor Zipper where
  map f (Zipper ls c rs) = Zipper (map f ls) (f c) (map f rs)

iterateLeft :: forall a. Zipper a -> List (Zipper a)
iterateLeft = flip go Nil
  where
  go z@(Zipper Nil _ _) accum = z : accum
  go z@(Zipper (l:ls) c rs) accum = go (Zipper ls l (c:rs)) (z : accum)

iterateRight :: forall a. Zipper a -> List (Zipper a)
iterateRight = flip go Nil
  where
  go z@(Zipper _ _ Nil) accum = z : accum
  go z@(Zipper ls c (r:rs)) accum = go (Zipper (c:ls) r rs) (z : accum)

instance extendZipper :: Extend Zipper where
  extend f z = Zipper (map f $ drop 1 $ iterateLeft z) (f z) (map f $ drop 1 $ iterateRight z)

instance comonadZipper :: Comonad Zipper where
  extract (Zipper _ c _) = c
```

# おまけ２：ComonadとMonad

Comonadは“Co”monadというくらいですから、Monadと関係があります。

実際ComonadとMonadは**双対（dual）**になります。

ここではComonadとMonadの間にどういった関係があるのか、簡単なイメージを説明します。

## 型の対応

ComonadとMonadの対応を、それぞれの**型を見る**ことで考えてみます。

まず、ComonadとMonadがそれぞれ**実装する必要のある関数**を見ます。

```haskell
-- Monad
pure :: forall a m. Monad m => a -> m a
join :: forall a m. Monad m => m (m a) -> m a
bind :: forall a b m. Monad m => m a -> (a -> m b) -> m b

-- Comonad
extract :: forall a w. Comonad w => w a -> a
duplicate :: forall a w. Comonad w => w a -> w (w a)
extend :: forall a b w. Comonad => (w a -> b) -> w a -> w b
```

HaskellやPureScriptを知らない人は`forall a m. Monad m =>`のところが読みにくいと思いますが、とりあえずそこは無視して後ろだけ見てください。

まずpureとextractです。

```haskell
pure :: a -> m a
extract :: w a -> a
```

`m`と`w`を読み替えれば、**`->`が反対**になっていますね。

次に`join`と`duplicate`を見てみます。

```haskell
join :: m (m a) -> m a
duplicate :: w a -> w (w a)
```

これも`m`と`w`を読み替えれば、**`->`の向きを逆にしたもの**になっていますね。

最後に`bind`と`extend`です。

```haskell
bind :: m a -> (a -> m b) -> m b
extend :: (w a -> b) -> w a -> w b
```

このままではちょっとわかりづらいですね。
ということで、`extend`の**引数の順番を変えてみます**。

```haskell
bind :: m a -> (a -> m b) -> m b
extend :: w a -> (w a -> b) -> w b
```

だいぶん見えてきましたね。
最後に、わかりやすいよう`extend`の`a`と`b`を入れ替えてみます。

```haskell
bind :: m a -> (a -> m b) -> m b
extend :: w b -> (w b -> a) -> w a
```

これで`bind`と`extend`も、`m`と`w`を読み替えれば**`->`の向きが反対なだけの関係**になりましたね。

## 具体例

Comonadの例として**Zipper**を、Monadの例として**List**を考えます。

```haskell
-- Monadの例（List）
pure :: forall a. a -> List a
pure x = x : Nil

join :: forall a. List (List a) -> List a
join Nil = Nil
join (xs:xss) = xs <> (join xss)

bind :: forall a b. List (List a)
bind xs f = join (map f xs)

-- Comonadの例（Zipper）
extract :: forall a. Zipper a -> a
extract (Zipper ls c rs) = c

duplicate :: forall a. Zipper a -> Zipper (Zipper a)
-- 省略

extend :: forall a b. (Zipper a -> b) -> Zipper a -> Zipper b
-- 省略
```


### MonadとしてのList

`pure`は**要素を1つ受け取って、それだけをもつListを作る**関数ですね。
`singleton`という名前で定義されることがあります。

`join`は、ListのListを**すべて結合して1つのListにしてしまう**関数です。
`flatten`などと呼ばれることが多いです。

最後に`bind`ですが、少しイメージがしづらいかもしれません。

実は、

```haskell
bind xs f = join (map f xs)
```

となります。

型を見てみると、

```haskell
map :: (a -> b) -> List a -> List b
join :: List (List a) -> List a
bind :: List a -> (a -> List b) -> List b

xs : List a
f :: a -> List b
bind xs f :: List b

map f :: List a -> List (List b) -- map の b を List b とみる
map f xs :: List (List b)
join (map f xs) :: List b

bind xs f = join (map f xs)
```

となり、確かに`bind xs f = join (map f xs)`となりそうですね。

つまり、`bind`はListと「**要素1つを受け取ってListを返す**」ような関数を受け取り、その関数を**すべての要素に適用**し、またその**結果のListをすべて結合する**、という処理になります。

### ComonadとしてのZipper

`extract`は、Zipperが現在**注目している要素を取り出す**関数でしたね。

`duplicate`は、**すべての要素についてその要素に注目したZipperをもってきて、それらのZipperを作る**関数でした。

`extend`は`duplicate`と`map`に分解することができて、

```haskell
extend f z = map f (duplicate z)
```

でしたね。

なんだか[MonadとしてのList](#monadとしてのlist)で似たような説明を見た気がしますね。

### 対応

```haskell
pure :: forall a. a -> List a
extract :: forall a. Zipper a -> a
```

`pure`は「**1つの要素からListを作る**」関数でした。

そして、`extraxt`は「**Zipperから注目している要素を（1つ）取り出す**」関数でしたね。

```haskell
join :: forall a. List (List a) -> List a
duplicate :: forall a. Zipper a -> Zipper (Zipper a)
```

`join`はListのListを、**すべて結合して1つのListにまとめてしまう**関数でした。
つまり「**重なりを潰す**」関数ですね。

`duplicate`はすべての要素について、**それに注目したZipperをもってきて、それらのZipperを作る**関数でしたね。
つまり、Zipperを「**重ねる**」関数です。

```haskell
bind :: forall a b. List a -> (a -> List b) -> List b
extend :: forall a b. (Zipper a -> b) -> Zipper a -> Zipper b
```

`bind`と`extend`はそのままではわかりづらいですね。

ここで、`bind`は`map`と`join`、`extend`は`map`と`duplicate`で書き換えられたことを思い出します。

```haskell
bind f xs = join (map f xs)
extend f z = map f (duplicate z)
```

`bind`は「**それぞれの要素に`f :: a -> List b`を適用してから、重なりを潰す**」関数ですね。

`extend`は「**Zipperを重ねてから、それぞれの要素（Zipper）に`f :: Zipper a -> b`を適用する**」関数となりますね。

どうでしょう、具体例を見ることで、少しだけ対応関係のイメージが掴みやすくなったでしょうか。

## まとめ

こういったComonadとMonadのような、**矢印の向きを反対にした関係**を、圏論の用語で**双対**と言うそうです。

ただ、矢印は必ずしも関数というわけではありません。
説明できる自信がないのでここでは触れませんが、気になる人は圏論を学んでみると良いかもしれません。