本当に雑に(前半部分だけを)まとめただけなので、ちゃんと知りたい人は、元動画やライブラリのコードや、元論文読むとよいです
- http://hackage.haskell.org/package/discrimination
- https://www.youtube.com/watch?v=cB8DapKQz-I
- https://github.com/ekmett/contravariant/blob/v1.3.2/src/Data/Functor/Contravariant/Divisible.hs
やる気がでたら、もう少し真面目な解説を後で別に書くかも知れませんし、書かないかもしれません。
先に簡単に自分の感想的なものを書いておきます。
ソートの話なはず、の動画を見ていたら、なぜか前半は「圏論」や「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 ✕ b) -> c) ✕ f a ✕ g b -> Day f g c
( ^ω^) < 以下のようにすると、ContravariantなDayじゃなイカ?そう思うじゃろ?
data Day f g a where Day :: f (c -> (a ✕ b)) ✕ f a ✕ 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のライブラリの本当の説明なのだが、つかれたので、今回の要約はここまで