挿入ソートと選択ソートは双対

先日 [Gotanda.hs #1 @HERP](https://herp-inc.connpass.com/event/153651/) というイベントがあって、そこで[Recursion Schemesで考える並べ替えアルゴリズム](https://speakerdeck.com/lotz84/recursion-schemesdekao-erubing-beti-earugorizumu)というタイトルで[A Duality of Sorts](https://www.cs.ox.ac.uk/ralf.hinze/publications/Sorting.pdf)という論文の話をLTしたんですが、この記事ではそこで話せなかった論文の後半で解説されている**挿入ソートと選択ソートの双対性**について書いていきたいと思っています。

ソートアルゴリズムの復習
------------------
まずは主役の二人である挿入ソートと選択ソートについて見ていきましょう。

**挿入ソート**は与えられたリストの先頭から要素を取り出し、これまでに構築したソート済みのリストに挿入していくという処理を繰り返すことでソートを実現するアルゴリズムです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/99cd3e0b-c9f5-ba10-8746-567d83dd55f8.gif" width=300px/>
出典: [Insertion sort - Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort)


これをHaskellで実装すると以下のようになります。

```hs
insertSort :: [Int] -> [Int]
insertSort xs = go [] xs
  where go ys []     = ys
        go ys (x:xs) = go (insert x ys) xs

insert :: Int -> [Int] -> [Int]
insert x ys = xs ++ [x] ++ zs
  where (xs, zs) = span (<= x) ys
```

もう一方の**選択ソート**は与えられたリストから最小値を選択し先頭に並べ、残りのリストにも同様の処理を繰り返すことでソートを実現するアルゴリズムです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/d6ca15bc-d795-157d-9431-5b0592d748b8.gif" width=80px />
出典: [Selection sort - Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort)


これをHaskellで実装すると以下のようになります。

```hs
selectSort :: [Int] -> [Int]
selectSort xs = go (select xs)
  where go Nothing         = []
        go (Just (x, xs')) = x : go (select xs')

select :: [Int] -> Maybe (Int, [Int])
select [] = Nothing
select xs = Just (x, xs')
  where x  = minimum xs
        xs = delete x xs
```

いずれのソートアルゴリズムも`go`という関数を使って再帰的に処理を実行するような実装になっていることがわかります。このような再帰関数はアルゴリズムを記述するための強力な道具である一方で、使い方を間違えるとgotoのように必要以上の複雑さを実装に持ち込んでしまう危険性もあります。そのため実装の中にある再帰的な構造（Recursion Scheme）だけを抽象的な関数として切り出すことで、プログラマが再帰的なパターン以外の実装に集中できるようにすることは有用でしょう。例えばGHCで標準的に使えるパッケージbaseが提供する`foldr`, `unfoldr` という関数を使えば先程のソートアルゴリズムは

```hs
insertSort = foldr insert []
selectSort = unfoldr select
```

というふうに実装することができます。実装が再帰的な構造以外の部分`insert`, `select`に集中できているのでとても簡潔に書くことが出来ました。もっと一般的な再帰アルゴリズムを考えると`foldr`, `unfoldr`だけでは不十分で、より多くの再帰的な構造を表す関数が必要になってきます。これらの再帰的な構造を表す関数を扱う理論が次節で説明するRecursion Schemesなのです。

速習Recursion Schemes
---------------------
これ以降の話を理解するためにはRecursion Schemesの基本的な事柄について知っておく必要があるので簡単におさらいしておきましょう。

そもそも再帰的な構造がどこから現れるのかを考えると、型それ自体に再帰的な定義が現れていることに気がつきます。例えばHaskellにおけるリストの型定義は

```hs
data [] a = [] | a : [a]
```

と定義されていて、（特殊な構文のおかげで`[] a`, `[a]`と見た目は変わっていますが）再帰的にリストの型が定義に現れているのが分かります。

この型を再帰的でない型と再帰的な型に分解してみましょう。

```hs
-- | 再帰的でない型
data ListF a r = Nil | Cons a r
               deriving Functor -- r について関手になる

-- | 再帰的な型
newtype Fix f = In {out :: f (Fix f)}

-- | これは [a] と同型になる
type List a = Fix (ListF a)
```

`Fix`と`ListF`を組み合わせた`List`は実はリスト`[a]`と同型になることが分かります。すなわち情報を落とすことなくお互いの型の値を行ったり来たりすることが出来るのです。

```hs
toList :: List a -> [a]
toList (In Nil)         = []
toList (In (Cons x xs)) = x : toList xs

fromList :: [a] -> List a
fromList []     = In Nil
fromList (x:xs) = In (Cons x (fromList xs))
```

リストをわざわざ２つの方に分けた理由は`Fix`が持つ特殊な性質にあります。`Fix`はリストという型には依存しておらず、`Type -> Type`というカインドを持つ高階型に自分自身を再帰的に適応するというパターンを抜き出した抽象的な型です。実はこの`Fix`が持つ性質を利用すると`foldr`や`unfoldr`のような再帰的なパターンを統一的に議論できる土台を作ることが出来るのです。

### Catamorphism
`Fix`には newtype の定義より `In :: f (Fix f) -> Fix f` という関数が備わっています。実は `f a -> a` という関数には**f代数**という名前がついていて、`Fix f` は任意のf代数`f a -> a`を持ってくると`Fix f -> a`という関数を作ることが出来るという性質を持っています。このf代数から`Fix f -> a`への対応付けのことを**Catamorphism**と呼びます。ここでの登場人物を図に書くと以下のような可換図式になります。

<img width="300" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/9c63b105-7484-cee1-1977-bf8fa14bbb86.png">

`In`とは逆向きの`out :: Fix f -> f (Fix f)`という関数があるので、可換図式を`Fix f`から`a`まで左側をぐるっと経由することによって`cata`を実装することが出来ます。

```hs
cata :: Functor f => (f a -> a) -> Fix f -> a
cata g = g . fmap (cata g) . out
```

具体的に`Fix ListF`における`cata`の挙動を見てみましょう。例えば先程実装した`toList :: List a -> [a]`という関数は`cata`を使うと

```hs
toList :: List a -> [a]
toList = cata $ \case
  Nil         -> []
  (Cons x xs) -> x : xs
```

と書くことが出来ます。実は `foldr :: (a -> b -> b) -> b -> [a] -> b` における `(a -> b -> b)` に対応する部分を `Cons` の場合の処理で、 第二引数である `b` に対応する部分を `Nil` の場合の処理で与えてやっていると考えると、`List`における`cata`はまさに`foldr`と対応するのです。そういう意味ではCatamorphismはリストにおける`foldr`の一般化であるとも考えることが出来ます。

### Anamorphism
`Fix`には newtype の定義より `out :: Fix f -> f(Fix f)` という関数が備わっています。実は `a -> f a` という関数には**f余代数**という名前がついていて、`Fix f` は任意のf余代数`a -> f a`を持ってくると`a -> Fix f`という関数を作ることが出来るという性質を持っています。このf余代数から`a -> Fix f`への対応付けのことを**Anamorphism**と呼びます。ここでの登場人物を図に書くと以下のような可換図式になります。

<img width="300" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/33567d8a-ad9b-7fe4-54b7-5a6c101b057e.png">

`out`とは逆向きの`In :: f (Fix f) -> Fix f`という関数があるので、可換図式を`a`から`Fix f`まで左側をぐるっと経由することによって`ana`を実装することが出来ます。

```hs
ana :: Functor f => (a -> f a) -> a -> Fix f
ana g = In . fmap (ana g) . g
```

具体的に`Fix ListF`における`ana`の挙動を見てみましょう。例えば先程実装した`fromList :: [a] -> List a`という関数は`ana`を使うと

```hs
fromList :: [a] -> List a
fromList = ana $ \case
  []     -> Nil
  (x:xs) -> Cons x xs
```

と書くことが出来ます。実は `unfoldr :: (b -> Maybe (a, b)) -> b -> [a]` における第一引数である関数の返り値は`Nothing`もしくは`Just (a, b)`ですがこれらが`Nil`と`Cons x xs`に対応していると考えると、`List`における`ana`はまさに`unfoldr`と対応するのです。そういう意味ではAnamorphismはリストにおける`unfoldr`の一般化であるとも考えることが出来ます。

ところで、ここまでのAnamorphismの説明は先程のCatamorphismの説明とほとんど同じ構造になっていることに気づきましたでしょうか？特に可換図式を見てみると型の位置は変わらずに関数の向きだけが変わっていることに気がつくと思います。実はこのような関係にある２つの概念を**双対**の関係にあると呼んだりします。これは詳しく説明すると圏論由来の概念で、他にも有名な例としてはタプル`(a, b)`と`Either a b`が双対の関係にあったりします[^1]。

### Paramorphism
全ての再帰的な関数を`foldr`と`unfoldr`で実装できるわけではありません。**Paramorphism**はCatamorphismでは直接扱うことが出来なかった再帰的なパターンを扱うことが出来るRecursion Schemesです[^2]。例えば`tails`という関数を`List`のCatamorphismで実装することを考えてみましょう。

```hs
> tails [1,2,3]
[[1,2,3],[2,3],[3],[]]
```

やってみるとすぐに気が付きますが、Catamorphismは再帰のその時点における値全体を扱うことが出来ないので`tails`を実装することは難しいです。そこでその時点における値全体も再帰的なパターンの中で参照できるようにしたのがParamorphismです。

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/8a2b8edf-341a-0cb9-004e-4ecff1f532d8.png" />

Catamorphismの時と同様に可換図式の一番外を反時計回りにぐるっと辿ると`para`が実装できます。

```hs
para :: Functor f => (f (Fix f, a) -> a) -> Fix f -> a
para g = g . fmap (id &&& para g) . out
```

ここで`&&&`は`Control.Arrow`で提供されている

```hs
(&&&) :: (a -> b) -> (a -> c) -> a -> (b, c)
```

おおよそ上記のような型の演算子です。

早速`para`を使って `tails` を実装してみましょう。まずは`List a`に関する便利な関数をいくつか用意しておきます。

```hs
nil :: List a
nil = In Nil

cons :: a -> List a -> List a
cons x xs = In (Cons x xs)
```

これらを使って`tails`は以下のように作ることが出来ます。

```hs
tails :: List a -> List (List a)
tails = para $ \case
  Nil             -> cons nil nil
  Cons x (ys, xs) -> cons (cons x ys) xs
```

実際に `Data.List` の `tails` と同じ挙動になっているかどうか確認してみましょう。


```hs
> fmap toList . toList . tails . fromList $ [1,2,3]
[[1,2,3],[2,3],[3],[]]
```

うまく動いてそうですね :clap: 

### Apomorphism
Catamorphismの双対としてAnamorphismがあったように、Paramorphismの双対として**Apomorphism**があります。

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/d7efa197-b3b9-eeed-1c45-86044e9a68c4.png" />

`apo`の場合も同様に可換図式の外側をぐるっと時計回りに辿るように実装します。

```hs
apo :: Functor f => (a -> f (Either (Fix f) a)) -> a -> Fix f
apo g = In . fmap (id ||| apo g) . g
```

ここで`|||`は`Control.Arrow`で提供されている

```hs
(|||) :: (a -> c) -> (b -> c) -> Either a b -> c
```

おおよそ上記のような型の演算子です。

Apomorphismの型をよく見ると`Either`を使ってこれから組み立てる`Fix f`の型をそのまま返せるような機構が含まれているのが分かります。実はこのショートカットのような仕組みを使うことによってこれから紹介するソートアルゴリズムにおけるナイーブな挿入ソートを通常の挿入ソートの実装にすることが出来るのです。それではいよいよこれまで定義したRecursion Schemesを使って挿入ソートと選択ソートをどのように実装することが出来るのか見ていきたいと思います。

※Recursion Schemesはここで紹介した4つの以外にもまだまだたくさん便利なパターンが存在しており、さらにはモナドやコモナドとの相互作用があったり、全てを統一しようとする大統一理論があったり大変深く面白い世界が広がっている分野です。興味がある人は[Recursion Schemesで検索](https://www.google.co.jp/search?q=Recursion%20Schemes)したり、[Recursion Schemes - haskell-shoen](https://scrapbox.io/haskell-shoen/Recursion_Schemes)に俯瞰的にまとめられていたりするので参照してみて下さい。またhaskell-shoenはScrapboxで作られており誰でも編集が出来るので面白い話があればどんどん書き込んでいきましょう :muscle: 

ソートアルゴリズム再訪
----------------
まずソート済みのリストとそうでないリストを区別するためにソート済みのリストを表す型を定義しておきます。

```hs
data SListF a r = Nil' | Cons' a r
                deriving Functor

-- | ソート済みのリストを表す型
type SList a = Fix (SListF a)

nil' :: SList a
nil' = In Nil'

cons' :: a -> SList a -> SList a
cons' x xs = In (Cons' x xs)
```

`SListF`や`SList`の型を見るとすぐに分かると思いますが`ListF`や`List`と実質全く同じもので、主にリストがソート済みかどうかを名前で区別出来るように使い分けていきます。

さて準備が整ったのでソートアルゴリズムについて考えていきましょう。一般的なソートアルゴリズムは

```hs
sort :: Ord a => List a -> SList a
```

という型をしています。`List a`と`SList a`が`Fix`によって組み立てられていたことを思い出すと、

```hs
sort :: Ord a => Fix (ListF a) -> Fix (SListF a)
```

こうなります。

ところで`Fix f -> a`という型の関数はCatamorphismの結果として作ることが出来たので

```hs
sort :: Ord a => Fix (ListF a) -> Fix (SListF a)
sort = cata (? :: Ord a => ListF a (Fix (SListF a)) -> Fix (SListF a))
```

のように`cata`を使って型を分解することが出来ます。この時、`cata`に適用するために必要な関数`?`は`Ord a => (ListF a (SListF a)) -> Fix (SListF a)`という型です。さらにこの`?`の型は`a -> Fix f`という型になっており、これはApomorphismの結果として作ることが出来たので[^3]

```hs
sort = cata $ apo ??
  where ?? :: Ord a => ListF a (Fix (SListF a)) -> SListF a (Either (Fix (SListF a)) (ListF a (Fix (SListF a))))
```

と分解することが出来ます。最後に型の見え方が対称的になるように`??`に少し手を加えると、

```hs
sort = cata $ apo (??? . fmap (id &&& out))
```

となり、最終的には

```hs
??? :: Ord a
    => ListF a (SList a, SListF a (SList a))
    -> SListF a (Either (SList a) (ListF a (SList a)))
```

という型の関数があれば`sort`関数と同じ型を`cata`と`apo`を使って構築できることが分かりました。
（うひゃー見た目が複雑 :joy: ですが心の目を凝らしてみると構造が見えてくるはず…？）

今度は反対に`sort`をAnamorphismの結果として出てくる関数だとして見てみましょう。

```hs
sort :: Ord a => Fix (ListF a) -> Fix (SListF a)
sort = ana (? :: Ord a => Fix (ListF a) -> SListF a (Fix (ListF a)))
```

`ana`に適用するのに必要な関数`?`は`Ord a => Fix (ListF a) -> SListF a (Fix (ListF a))`という型になりました。さらにこの`Fix f -> a`という型の関数はParamorphismの結果として作ることが出来たので[^4]

```hs
sort = ana $ para ??
  where ?? :: Ord a => ListF a (Fix (ListF a), SListF a (Fix (ListF a))) -> SListF a (Fix (ListF a))
```

と分解することが出来ます。最後に型の見え方が対称的になるように`??`に少し手を加えると、

```hs
sort = ana $ para (fmap (id ||| In) . ???)
```

となり、最終的には

```hs
??? :: Ord a
    => ListF a (List a, SListF a (List a))
    -> SListF a (Either (List a) (ListF a (List a)))
```

という型の関数があれば`sort`関数と同じ型を`ana`と`para`を使って構築できることが分かりました。

２つの分解方法で必要になった結果`???`の型を目を凝らしてよく見てみると以下のような型を持つ関数が共通して必要になっていることが分かります。

```hs
swop :: Ord a => ListF a (x, SListF a x) -> SListF a (Either x (ListF a x))
```

引数と返り値で、`ListF a`と`SListF a`の順番が、そしてタプル`(,)`と`Either`が双対として入れ替わっているのが分かりますね。それではこの`swop`を実装してみましょう。

```hs
swop :: Ord a => ListF a (x, SListF a x) -> SListF a (Either x (ListF a x))
swop Nil                = Nil'
swop (Cons a (x, Nil')) = Cons' a (Left x)
swop (Cons a (x, (Cons' b x')))
  | a <= b    = Cons' a (Left x)
  | otherwise = Cons' b (Right $ Cons a x')
```

この`swop`が型パズルの最後のピースであり、我々はソートアルゴリズムと同じ型を持つ2つの関数

```hs
cata $ apo (swop . fmap (id &&& out))

ana $ para (fmap (id ||| In) . swop)
```

を手に入れることが出来ました。

しかし本当にこれらはソートアルゴリズムになっているのでしょうか？実際に実行して確かめてみましょう。

```hs
> toList' . cata (apo (swop . fmap (id &&& out))) . fromList $ [4, 3, 9, 0]
[0,3,4,9]

> toList' . ana (para (fmap (id ||| In) . swop))  . fromList $ [4, 3, 9, 0]
[0,3,4,9]
```

見事リストをソートできていますね！ :clap:

それではこれら２つのソートアルゴリズムはどういった種類のアルゴリズムになっているのでしょうか？実際の挙動を調べるためにどのようにアルゴリズムが実行されたのかステップ毎にコードを評価して確認していきましょう。

### cata - apo - swop

```hs
cata (apo (swop . fmap (id &&& out)))
  (In (Cons 4 (In (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))))))))
```

`cata` は第一引数の関数で `In` を置き換えるような動作をするので、

```hs
apo f (Cons 4 (apo f (Cons 3 (apo f (Cons 9 (apo f (Cons 0 (apo f Nil))))))))
```

のように展開することが出来ます。

まずは内側から、 `apo f Nil`を評価すると

```hs
apo f Nil

== apo (swop . fmap (id &&& out)) Nil

== In . fmap (id ||| apo f) . (swop . fmap (id &&& out)) $ Nil

== In . fmap (id ||| apo f) $ swop Nil

== In $ fmap (id ||| apo f) Nil'

== In Nil'
```

となり結果の型はソート済みのリストを表す`SList a`であることが分かります。

次に一つ外側を含めた `apo f (Cons 0 (In Nil'))` を評価すると、

```hs
apo f (Cons 0 (In Nil'))

== In . fmap (id ||| apo f) . (swop . fmap (id &&& out)) $ (Cons 0 (In Nil'))

== In . fmap (id ||| apo f) $ swop (Cons 0 (In Nil', Nil'))

== In $ fmap (id ||| apo f) (Cons' 0 (Left (In Nil')))

== In (Cons' 0 (In Nil'))
```

となります。

次にさらに一つ外側を含めた `apo f (Cons 9 (In (Cons' 0 (In Nil'))))` を評価すると、

```hs
apo f (Cons 9 (In (Cons' 0 (In Nil'))))

== In . fmap (id ||| apo f) . (swop . fmap (id &&& out)) $ Cons 9 (In (Cons' 0 (In Nil')))

== In . fmap (id ||| apo f) $ swop (Cons 9 (In (Cons' 0 (In Nil')), Cons' 0 (In Nil')))

== In $ fmap (id ||| apo f) (Cons' 0 (Right (Cons 9 (In Nil'))))

== In $ Cons' 0 (apo f (Cons 9 (In Nil')))

== In (Cons' 0 (In (Cons' 9 (In Nil'))))
```

となりました。`swop`によって0と9の順番が入れ替えられていますね。

最後にもう一つだけ外側を持ってきて評価してみましょう。

```hs
apo f (Cons 3 (In (Cons' 0 (In (Cons' 9 (In Nil'))))))

== In . fmap (id ||| apo f) . (swop . fmap (id &&& out)) $ Cons 3 (In (Cons' 0 (In (Cons' 9 (In Nil')))))

== In . fmap (id ||| apo f) $ swop (Cons 3 (In (Cons' 0 (In (Cons' 9 (In Nil')))), Cons' 0 (In (Cons' 9 (In Nil')))))

== In $ fmap (id ||| apo f) (Cons' 0 (Right (Cons 3 (In (Cons' 9 (In Nil'))))))

== In . Cons' 0 $ apo f (Cons 3 (In (Cons' 9 (In Nil'))))

== In . Cons' 0 $ In . fmap (id ||| apo f) . (swop . fmap (id &&& out)) $ (Cons 3 (In (Cons' 9 (In Nil'))))

== In . Cons' 0 $ In . fmap (id ||| apo f) $ swop (Cons 3 (In (Cons' 9 (In Nil')), Cons' 9 (In Nil')))

== In . Cons' 0 $ In . fmap (id ||| apo f) $ Cons' 3 (Left (In (Cons' 9 (In Nil'))))

== In . Cons' 0 $ In (Cons' 3 (In (Cons' 9 (In Nil'))))

== In (Cons' 0 (In (Cons' 3 (In (Cons' 9 (In Nil'))))))
```

つまりこのアルゴリズムは内側からソート済みのリストを作り、どんどん一つ外側から要素をとってきて適切な位置まで並べ替えるという処理を繰り返してソートを行っているのです。これはまさに**挿入ソート**ですね！さらにApomorphismの`Either`をうまく使うことによって、適切な位置まで要素を挿入したあとの評価は打ち切って無駄な計算をしないような挙動が見て分かるかと思います。

```hs
insertSort :: Ord a => List a -> SList a
insertSort = cata $ apo (swop . fmap (id &&& out))
```

### ana - para - swop

```hs
ana (para (fmap (id ||| In) . swop))
  (In (Cons 4 (In (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))))))))

== In . fmap (ana f) . (para (fmap (id ||| In) . swop)) $ 
     (In (Cons 4 (In (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))))))))

== In . fmap (ana f) $
     (g (Cons 4
       ( In (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil))))))
       , g  (Cons 3
         ( In (Cons 9 (In (Cons 0 (In Nil))))
         , g  (Cons 9
           ( In (Cons 0 (In Nil))
           , g  (Cons 0
             ( In Nil
             , g  Nil
             )
           ))
         ))
       ))
     ))
```

さて大変なことになりましたが怯まずに内側から評価していくことにしましょう。まずは `g Nil` です。

```hs
g Nil

== fmap (id ||| In) . swop $ Nil

== fmap (id ||| In) Nil'

== Nil'
```

楽勝ですね :v:

次に外側の `g (Cons 0 (In Nil, Nil'))` を評価してみましょう。

```hs
g (Cons 0 (In Nil, Nil'))

== fmap (id ||| In) . swop $ Cons 0 (In Nil, Nil')

== fmap (id ||| In) $ Cons' 0 (Left (In Nil))

== Cons' 0 (In Nil)
```

リストのような式が出てきましたがソート済みというわけでもなさそうです。

次にもう一つ外側の `g (Cons 9 (In (Cons 0 (In Nil)), Cons' 0 (In Nil))` を評価してみましょう。

```hs
g (Cons 9 (In (Cons 0 (In Nil)), Cons' 0 (In Nil))

== fmap (id ||| In) . swop $ (Cons 9 (In (Cons 0 (In Nil)), Cons' 0 (In Nil))

== fmap (id ||| In) $ Cons' 0 (Right $ Cons 9 (In Nil))

== Cons' 0 (In (Cons 9 (In Nil)))
```

これは面白い挙動をしていますね。つまり返り値を見ると`Cons'`の第一引数にはこれまでの最小値が保持されていて、第二引数の型は`List a`ですが、ここには最小値以外の要素を持つリストがそのまま保持されているという挙動になっていそうです。どこかで見た振る舞いですよね :thinking: 

念の為、更に外側の `g (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))), Cons' 0 (In (Cons 9 (In Nil)))))` を評価してみましょう。

```hs
g (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))), Cons' 0 (In (Cons 9 (In Nil)))))

== fmap (id ||| In) . swop $ Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))), Cons' 0 (In (Cons 9 (In Nil))))

== fmap (id ||| In) $ Cons' 0 (Right $ Cons 3 (In (Cons 9 (In Nil))))

== Cons' 0 (In (Cons 3 (In (Cons 9 (In Nil)))))
```

予想通り最小値とそれ以外のリストのペアが出来上がっていますね。

この調子で最後まで評価すると全体は、

```hs
In . fmap (ana f) . (para (fmap (id ||| In) . swop)) $ 
  (In (Cons 4 (In (Cons 3 (In (Cons 9 (In (Cons 0 (In Nil)))))))))

== In . fmap (ana f) $ Cons' 0 (In (Cons 4 (In (Cons 3 (In (Cons 9 (In Nil)))))))

== In (Cons' 0 (ana f (In (Cons 4 (In (Cons 3 (In (Cons 9 (In Nil)))))))))
```

となり最小値を一番先頭に持ってきた上でそれ以外のリストに対して再帰的に同様のアルゴリズムを適用しているのが分かるかと思います。これはまさに**選択ソート**ですね！！

```hs
selectSort :: Ord a => List a -> SList a
selectSort = ana $ para (fmap (id ||| In) . swop)
```

ここが山頂です。お疲れさまでした :clap: 
我々は`sort :: Fix (List a) -> Fix (SList a)`関数に対して双対な二つの関数により二通りに分解することにより挿入ソートと選択ソートが得られることを見てきました。つまりこの二つのソートアルゴリズムは双対の関係にあったということなのです！

おまけ: 挿入ソートと選択ソートは本当に双対なのか？
--------------------------------------
最後に双対の景色を俯瞰して終わりにしましょう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/17134/e2eabd6c-f83b-12a0-4fe6-a08f5bd7b6b0.png)

Catamorphism, Anamorphism, Paramorphism, Apomorphism それぞれの可換図式を組み合わせて、`insertSort`と`selectSort`が出来上がる様子を図示しました。図中の$L_a$は`ListF a`であり$S_a$は`SListF a`を意味しています。二つの図は真ん中の`swop`のところで別れており、$L_a \cong S_a$であり$+$と$\times$もまた矢印の向きを変えれば入れ替わることに注意すると、片方を180度回転させればちょうど矢印が反対向きになる形でピッタリと重なるのが分かると思います。とても綺麗ですね :clap: 


[^1]: [圏とHaskellの型](https://www.slideshare.net/KinebuchiTomo/haskell-63665717)
[^2]: 実はCatamorphismを使ってParamorphismを実装することも出来るのですがここでは割愛します。可換図式にヒントを入れておくので興味がある人は是非考えてみて下さい。
[^3]: ここでAnamorphismを選択すると結果はナイーブな挿入ソートになります。
[^4]: ここでCatamorphismを選択すると結果はバブルソートになります。詳しい解説は[Recursion Schemesで考える並べ替えアルゴリズム](https://speakerdeck.com/lotz84/recursion-schemesdekao-erubing-beti-earugorizumu)を参照してみて下さい。