ファンクターとアプリカティブファンクター（解決編）

引き続き Haskell。
前回はこちら。
Applicative、pure、関数についての再考、帰ってきた Functor - doitakaの日記

タネ本は『すごいHaskellたのしく学ぼう!』。

作者: ＭｉｒａｎＬｉｐｏｖａｃａ
出版社/メーカー: オーム社
発売日: 2017/07/14
メディア: Kindle版
購入: 4人クリック: 9回
この商品を含むブログを見る

あらすじ

これまで、「関数がファンクターである」という点についての検証から出発し、アプリカティブファンクターの辺りで頓挫。紆余曲折あった結果、関数にとっての文脈とはつまりは引数ではないか、という考え方に至る。

関数に引数を与える、という見方により、普通の値の関数適用($)、ファンクターの fmap (<$>)、アプリカティブファンクターの (<*>) を見直してみようとしたものの <$> でとりあえず混乱し、一度筆を置く。

($) :: (a -> b) -> a -> b
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

以下、とりあえずファンクターから見直し。
「解決編」と銘打ったが、本当に解決できるかは定かでなし。

ファンクターとはなんぞや（再）

前々回に、ファンクターとは何であるか、を考えてみたわけだが、その時の自分なりのまとめはこうであった。

「ファンクター値」と言っているからアレだが、コードをそのまま読めば、「型コンストラクタに具体型が適用されてできた具体型の値」である。
この、型コンストラクタの部分が fmap の結果失われない、ということが、Functor の性質ということのようである。

コードそのまま読んでるような言い方なので、理解しているとは言い難いかもしれないが、コードそのままなので、そこまで外してもないように見える……。
要点を抜き出せば、「fmap の結果失われない」である。

で、前回、

(<$>) :: Functor f => (a -> b) -> f a -> f b

から、図にしてみたのがコレである。

ファンクターの F の部分が <$> の後に引き継がれる点が、通常の関数適用と異なっている。
この図では F を「値をくるむもの」というイメージで示しているが、本当にこの見立てで良いのかはまだなんとも言えない。

以降、具体例を挙げてみる。

関数ファンクターの場合

g :: r -> a
f :: a -> b

とした場合、

 f <$> g = f . g

である。
この場合を以下に図示してみる。

関数合成を図示しただけ、という感じにはなったが。
この図と、前出のファンクター一般についての図の対応を取った際、 F に相当するのは、「r 型の x を与えることができる」という点である。
同じ x で表しているから紛らわしいが、ファンクター一般の図で関数 f に与えられていた値 x に相当するのは、今回は関数 g である。関数ファンクターの図の方では、値 x は将来において与えられる可能性があるだけで、<$> の時点ではまだ存在していない。
関数 g が持っていた、「r 型の値が未来に与えられる可能性」は、<$> の結果得られる f . g にも引き継がれている。
これは、特に違和感のない、素直な文脈の引き継ぎに見える。

少々ややこしいのは、関数が箱的であることと、ファンクターとしての関数において文脈が「くるむもの」的であることとが別の概念である、というところだろうか。
関数 g は、箱的な値で r 型の値を取るという文脈を持つ。関数が箱的な値である、という点から g に f が与えられる、というイメージで見ると、 g . f になり、r 型の値を取るという文脈 or 性質が失われてしまう。
関数ファンクターで引き継がれるのは、引数として r 型の値を取る、という点であり、関数が箱的であるというイメージとは若干ずれる。

リストファンクターの場合

xs :: [a]
f :: a -> b

とした場合、

f <$> xs = map f xs

である。

リストは、への : 演算の適用が繰り返されたもの、とも言えるので、
仮に、xs = [x, y, z] = x : y : z : であるとして図示すると以下となる。

分かってきたような気がしてきた。
まず、[a] 型のリストとは、「a 型の値の後に、[a] 型のリストがくっついたもの」とみなせる。そして [a] 型のリストには、空リスト [] も含まれるとし、再帰的に定義を当てはめれば無限に続くリストが構成できる。
リストにおいて、前出図のファンクターの F に相当するのは、x から見て「後に [a]型のリストがくっついていること」である。そして、「後にくっついているリスト」は再帰的に、空リストになるまで処理される、ということである。
つまり、リスト x : xs を、文脈をもった値とみなす場合、「値」は x であり、「文脈」は : xs の部分である。そして、 <$> においては、文脈は再帰的に消化される。

先ほどのリストファンクターの図を、再帰的に文脈が処理されるという見方で書きなおせば以下となる。

リストにおいては、文脈は、「値の後ろにリストが付いている構造が再帰的に繰り返される」であり、これを関数に <$> する場合は、「構造を維持しつつ再帰的に関数に値を与えよ」ということになる。

ファンクター則

以上、関数とリストの例を確認してみた。<$> によって関数にファンクター値を与えた際、関数適用の結果生み出される値にファンクター値の文脈が引き継がれる、ということについてイメージがつかめた。

この流れで、ファンクター則についても確認してみる。
Control.Monad ドキュメントより、ファンクター則は以下の２つである。

fmap id == id
fmap (f . g) == fmap f . fmap g

これについて、関数適用を $ 、 fmap を <$> に置き換えると、

id <$> == id $
((f $) . (g $)) <$> == (f <$>) . (g <$>)

となる。

第１法則は id 関数に与えた場合の動作である。
id 関数は与えられた値と同じものを生み出す関数だが、 $ でこの関数にファンクター値を与えた場合は、定義より、全く同じファンクター値が得られるはずである。では、特殊形である <$> で与えた場合にどうなるか、という時に、文脈が正しく維持されるのであれば id $ と同じ結果になるはず、ということである。つまり、文脈の維持という動作を保証する法則となる。

第２法則は、関数合成のケースである。
左側では、合成された一つの関数に <$> でファンクター値を与えている。
右側では、<$> によって関数にファンクター値を与える、という関数を合成している。
つまりは、<$> が合成できることの保証、ということになるが、もっと言えば、「内側」の関数適用と、「外側」の文脈維持の操作が、それぞれ独立していることの保障、ともできるだろう。

以上、ひとまずファンクターについてはイメージがだいぶ固まってきた。
この流れでアプリカティブファンクターに入る。

アプリカティブファンクターとはなんぞや

冒頭の比較を再掲する。

($) :: (a -> b) -> a -> b
(<$>) :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b

アプリカティブファンクターでは、値を与える関数の方にも文脈が付いている、ということになる。
アプリカティブ値を、アプリカティブな関数に与えて、アプリカティブ値を生み出す、と言える。

ファンクターの際にならって図示してみると以下となる。

左側の関数の部分の描き方が少々微妙なことになっているが… F の中にある関数は b 型値を生み出す、という部分は従来どおりとし、関数全体が F の文脈の中にある、ということを表しているつもりである。

また、ファンクターの際は、文脈がファンクター値の側のみにあったため、型と値を区別せずに両方を F としてしまっていたが（これはミス……）、アプリカティブファンクターの場合は、文脈がアプリカティブ値とアプリカティブ関数の両方に存在するため、これを区別する目的で、 s, t, u を F 型のインスタンスとして表した。

そう、結局のところ <$> と <*> の差は、文脈の登場が１回であるか２回であるかの差ということになる。
x の文脈 s と、f の文脈 u が、言うなれば「衝突する」のが <*> の場合である。
文脈のレベルにおいて、２つのものを１つにする操作が <*> の中で起きている、と見ることでアプリカティブファンクターを理解することができるのではないだろうか？　これは、文脈の演算、または、文脈の合成、と言えそうである。

では、ファンクターの場合と同様に、関数、リストのケースを見てみよう。

関数アプリカティブファンクターの場合

アプリカティブファンクターとしての関数において宣言がどうなるか。
宣言はこう、

    pure :: a -> (r -> a)
    (<*>) :: (r -> (a -> b)) -> (r -> a) -> (r -> b)

実装はこうなる。

instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)

『すごい』に出てきた例

Prelude Control.Applicative> :t (+) <$> (+3) <*> (*100)
(+) <$> (+3) <*> (*100) :: Num b => b -> b
Prelude Control.Applicative> (+) <$> (+3) <*> (*100) $ 5
508

『すごい』の説明。

(+) <$> (+3) <*> (*100) と書くと、「引数を (+3) と (*100) に渡し、２つの結果に対して + を使う」関数が出来上がります。

この時点では分かったような、分からないような…というところ。
なぜかこの例では、 <$> してから <*> している。
では、<*> を単体で使うとどうなるか、というとこうなる。

Prelude Control.Applicative> :t (+) <*> (+3)
(+) <*> (+3) :: Num b => b -> b
Prelude Control.Applicative> (+) <*> (+3) $ 5
13

？？？というところだが、((<*>) f g) x = f x (g x) に当てはめれば、5 + (5+3) である。ここには、引数の 5 が２回登場している。
先ほどの、(+) <$> (+3) <*> (*100) では、(5+3) + (5*100) であったところだが、関数の数がひとつ少ないので、5 がそのまま登場した、ということになる。

動作をはっきり見せるために id 関数を使うと、こうである。

Prelude Control.Applicative> (+) <*> id $ 5
10

関数アプリカティブファンクターの動きを図にまとめてみると以下となる。

おぉぉ…。まとめてみると以下と言えそうである。
関数 g と関数 f を <*> で合成する際、「r 型値 x を取る」というそれぞれの文脈を維持するため、 f <*> g が取った引数 x を複製して f と g それぞれに与える形で合成が行われている、と。
つまり、関数アプリカティブファンクターでは、文脈の衝突が、文脈を複製することでそれぞれを維持する、という形で解消されている、となる。

では、pure をこれに絡めた場合はどうなるか？
前回記事で見たが、 pure x は定数のような動きをする。
これを１引数関数に対して使うと、「引数を２つ取るが１つの引数は無視して１引数関数のように振る舞う」関数ができる。
よって、以下の挙動となる。

Prelude Control.Applicative> pure (+3) <*> (*100) $ 5
503

『すごい』のアプリカティブ則の説明にもあったが、 pure f <*> x = fmap f x である。
よって、pure (+3) <*> (*100) = (+3) <$> (*100) = (+3) . (*100) となる。

ここでは、pure (+3) と (*100) が、<*> の対象で、「5 を取る」という文脈は衝突しているが、pure の働きにより (*100) の方の文脈だけが維持された、と見ることができる。
つまり、アプリカティブファンクターにおける pure は、文脈が衝突するケースで特殊な働きをするもの、と見れないか。

リストアプリカティブファンクターの場合

引き続き、リストの場合を見てみよう。
『すごい』の説明から、リストの実装はこうなる。

instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]

実行例は以下。

Prelude Control.Applicative> [(*0),(+100),(^2)] <*> [1,2,3]
[0,0,0,101,102,103,1,4,9]

結果として得られるリストは、 fs と xs の直積になる。

これを図示すると以下である。

文脈の衝突という比喩をこれに当てはめるならば、「後ろにリストがくっついている」という文脈が衝突した際に、後ろにくっついているものが全て残る形（＝直積）にすることで文脈の衝突を解消している、と言える。
リストの場合、pure x で得られるのは要素がひとつのリスト（空リストがくっついた値）なので、直積をした際には、 pure x でない方の後ろにくっついているリストが同じ数だけ残る。こちらも pure と衝突させたことで文脈が維持された、と言えそうである。

また、『すごい』では、別の方法でアプリカティブファンクターになったリストとして、Zipリストを紹介している。

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)

細かい説明を省いて以下に動作を図示すれば、こうである。

こちらでは、文脈の衝突の解消は、短い方に合わせる、というやり方で行われている。
そして、 pure は、絶対に「短い方」にならないために無限リストになっている、となる。

ファンクターの場合は文脈は維持されるだけであったが、アプリカティブファンクターでは文脈は衝突し演算が発生する。
文脈の衝突を解消する方法は複数あるため、リストと Zipリストというように複数の <*> のやり方が出てくる、ということのようである。

アプリカティブ則

以上、関数、リストを見てきて、アプリカティブファンクターがどういうものかがようやくつかめてきた。
ファンクターがアプリカティブである、ということは、文脈と文脈が衝突した時の解消の仕方が定義されている、ということと見ればよさそうである。

上記を受けて、アプリカティブ則をみてみるとこうである。

identity
    pure id <*> v = v
composition
    pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
homomorphism
    pure f <*> pure x = pure (f x)
interchange
    u <*> pure y = pure ($ y) <*> u

ひとつひとつ見ていこう。

    pure id <*> v = v

文脈つきの値 v を、 pure id に与えた場合、v がそのまま残る、ということである。
ここでは、
　・　v の文脈の部分が pure によって得られた文脈と衝突した結果維持される
　・　v の文脈の中の部分が id 関数に与えられた結果、同じ値が生み出される
と見れる。

    pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

ここでは、u, v は文脈をもった関数で、w は文脈をもった値である。<*> は左結合であるとのことなので、左辺は、
　・　pure (.) <*> u <*> v によって、「u の文脈と v の文脈が合成された文脈の中に、u の文脈の中の関数と v の文脈の中の関数が合成されたものが入っている」ものが得られ、これに w を <*> で与えている。
であり、右辺は、
　・　v に w を <*> で与えてから、得られた値を、u に <*> で与えている。
である。
つまり、合成されたものの適用（左辺）と、順番にひとつずつ適用（右辺）が同じになる、ということである。
これは、通常の関数合成の場合の、 f . g $ x = f $ (g $ x) に対応する。

    pure f <*> pure x = pure (f x)

これはちょっとよく分からないが……。
文字通りに読めば、
　・ f を pure してから、 x を pure したものを <*> で与えるのと、f に x を $ で与えてから pure するのが同じ
ということになる。
通常の関数適用と、<*> の中の関数適用が同じものである、ということか？

    u <*> pure y = pure ($ y) <*> u

これは分かりやすい。
文脈の部分だけに注目すれば、左辺は、
　・ u の文脈に、<*> で pure の文脈を与えている
で、右辺は、
　・　pure の文脈に、 <*> で u の文脈を与えている
ということになる。

要は、アプリカティブ則は文脈に関する演算の性質を定めたもの、と言えそうである。

で、これらの性質はどこかで見たような……というところだが。
はい、モノイドである。

モノイドは、結合的な二項演算子（２引数関数）と、その演算に関する単位元からなる構造です。ある値がある演算の単位元であるとは、その値と何か他の値を引数にしてその演算を呼び出したとき、返り値が常に他の値のほうに等しくなる、ということです。1 は * の単位元であり、[] は ++ の単位元です。

まさに、先ほどみた <*> における pure の性質に合致する。
よって、アプリカティブファンクターの pure が引数として与えられた値に付け加えるのは「単位元の文脈」と言えるのではないか。

モノイドの定義。

class Monoid m where
    mempty  :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty

モノイド則

    mempty `mappend` x = x
    x `mappend` mempty = x
    (x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

モノイド則の１は、アプリカティブ則の１に対応する。
モノイド則の２は、アプリカティブ則で直接対応するものがないが、アプリカティブ則の１と４から導けそうである。
モノイド則の３は、アプリカティブ則の２に対応する。

つまり……アプリカティブファンクターは文脈がモノイドであるファンクター、ということになるのではないだろうか。
ようやくオチがついた気がする。

で、この後……

アプリカティブファンクターについて落ち着いたところで次はモナドだ、と行きたいところだが、アプリカティブ則について見た際に、↓の用語を思いっきり飛ばしていた。

identity
composition
homomorphism
interchange

identity : 単位元、composition : 合成、 interchange : 可換、というのは何となく分かるのだが、 homomorphism : 準同型、でウッとつまる。
調べてみると、準同型というのは代数系の用語らしく、そもそもモノイドというのも代数系の概念らしい。
http://ja.wikipedia.org/wiki/%E4%BB%A3%E6%95%B0%E7%9A%84%E6%A7%8B%E9%80%A0

Haskell といえば圏論というイメージだったが、圏論以前にも色々あるということか。

続きがあるかどうかも不明だが、とりあえずこれまで。