ekmett先生のdiscriminationというライブラリの動画を見たので雑に要約してみた

本当に雑に(前半部分だけを)まとめただけなので、ちゃんと知りたい人は、元動画やライブラリのコードや、元論文読むとよいです



やる気がでたら、もう少し真面目な解説を後で別に書くかも知れませんし、書かないかもしれません。


先に簡単に自分の感想的なものを書いておきます。
ソートの話なはず、の動画を見ていたら、なぜか前半は「圏論」や「Hask」や「Contravariantなんちゃら」の話してて
「あれ、見る動画間違ったのかな?」
と思ったのですが、何度も見てみると
「すげぇwwwwちゃんと話繋がってるwww でもこれ最初の圏論などの説明そこまで必要だったのかwww」
みたいに一人で面白くなって笑ってた(えっ気持ち悪っ)。みたいな日々を過ごしています。



本質部分のソートの原理も画期的ですごそうだし、前半の圏論やContravariantなんちゃらや、Day ConvolutionからのApplicativeの流れも、なんとなく雰囲気だけでもわかってくると楽しいですね。
そしてScalaに移植したい(が、果たして可能なのか)


あと、Dayというデータ構造以前もekmettライブラリで見たことあったけど、これって数学者?の名前が由来(Brian Dayさん)なんですね。(´・∀・`)へー


Radix(日本語だと基数ソート?) や American Flag のソートも、なんとなく知ってるくらいで詳しくないので解説は書きません、各自ググってください。
ただ、ソートアルゴリズムを可視化した面白い動画があるので、みるとよいかもです。
radix sortは1分55秒あたりに出てきます。



https://youtu.be/kPRA0W1kECg?t=1m55s



というわけで、ここからやっと本文的な何かです。





今日はソートとかの話するぞ
( ^ω^)




Radix とか American Flagっていうソートの方法があるのは知っているか?

( ^ω^)
Radix / American Flag ⊂




それは一旦置いておいて「モナドは単なる自己関手の圏におけるモノイド対象」じゃな?なにも問題ないな?
( ^ω^)
⊃ Monads are Monoid ⊂





(MonadsがMonoidなことや、Haskの説明などがあるが中略)





( ^ω^) < 次に Day Convolution ( http://ncatlab.org/nlab/show/Day+convolution )について考えるぞ
⊃ Day Convolution ⊂



( ^ω^) < これをHaskellコードにすると
≡⊃⊂≡


( ^ω^) < こんなやつじゃ

data Day f g a where
  Day :: f (a -> b) -> g a -> Day f g b


( ^ω^) < このシグネチャはApplicative・・・(色々省略




( ^ω^) < つまり、Dayを使ってゴニョゴニョすると、ApplicativeもMonadと同じようにMonoidsだということがわかるな?




( ^ω^) < ところで、FunctorにはContravariantなFunctorというものがあるな?
⊃ Contravariant Functor ⊂




( ^ω^) < ContravariantなFunctorがあるなら、Functor以外でもContravariantなものが存在するか?を考えてみたくなるじゃろ?





( ^ω^) < Dayはこんなものじゃったな?

data Day f g a where
  Day :: f ((a &#10005; b) -> c) &#10005; f a &#10005; g b -> Day f g c


( ^ω^) < 以下のようにすると、ContravariantなDayじゃなイカ?そう思うじゃろ?

data Day f g a where
  Day :: f (c -> (a &#10005; b)) &#10005; f a &#10005; g b -> Day f g c

( ^ω^) < あらためて「Contravaraintな〇〇」について考えるぞ



( ^ω^) < これは存在するか?
⊃ Contravariant な Monad


( ^ω^)
≡⊃⊂≡


( ^ω^) < 無理じゃな?
⊃    ⊂




( ^ω^) < じゃあComonadは?
⊃ Contravariant な Comonad ⊂


( ^ω^)
≡⊃⊂≡


( ^ω^) < それも無理じゃな?
⊃    ⊂





( ^ω^) < しかしContravariantなApplicativeは・・・?
⊃ Contravariant な Applicative ⊂


( ^ω^)
≡⊃⊂≡


( ^ω^)
⊃⊂

( ^ω^) < 存在するのじゃ!

_人人人人人人人人人人人人人_
> Contravariant な Applicative <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^Y^Y^Y ̄




( ^ω^) < ContravaiantなApplicativeを、Divisibleと呼ぶことにするぞ
⊃ Divisible ⊂


( ^ω^) < 同じようにContravaiantなAlternativeも作れるな?こっちはDecidableと呼ぶことにするぞ?
⊃ Decidable ⊂


( ^ω^) < まとめると、こうじゃ

class Contravariant f where
  contramap :: (a -> b) -> f b -> f a

class Contravariant f => Divisible f where
  divide  :: (a -> (b, c)) -> f b -> f c -> f a
  conquer :: f a

class Divisible f => Decidable f where
  choose :: (a -> Either b c) -> f b -> f c -> f a
  lose :: (a -> Void) -> f a


( ^ω^) < ここで、Boolを返す関数をPredicateという名前でnewtype作るぞ
newtype Predicate a = Predicate { getPredicate :: a -> Bool } ⊂




( ^ω^) < Predicateは、DecidableとDivisibleのインスタンスになるな?よいな?

instance Divisible Predicate where
  divide f (Predicate g) (Predicate h) = Predicate $ \a -> case f a of
    (b, c) -> g b && h c
  conquer = Predicate $ const True

instance Decidable Predicate where
  lose f = Predicate $ \a -> absurd (f a)
  choose f (Predicate g) (Predicate h) = Predicate $ either g h . f


( ^ω^) < あと、以下のようなもの色々用意しておくと、それらもさっきのclassのインスタンスになるな?
⊃ Equivalence, Op, Comparison ⊂

newtype Equivalence a = Equivalence { getEquivalence :: a -> a -> Bool }

newtype Op a b = Op { getOp :: b -> a }

newtype Comparison a = Comparison { getComparison :: a -> a -> Ordering }

( ^ω^) < ところでHaskellにはGHC.Genericsというものがあるな?
GHC.Generics



( ^ω^) < さて、これまでの

を組み合わせると、なんと(普通ソートというのは O(n log n) だったりするが)

_人人人人人人人人人人_
> O(n)のソートが実現 <
 ̄Y^Y^Y^Y^Y^Y^Y^Y^ ̄

できたりするのじゃ?すごいじゃろ?


ここまでが動画の半分くらいで、ここからがある意味discriminationのライブラリの本当の説明なのだが、つかれたので、今回の要約はここまで