読者です 読者をやめる 読者になる 読者になる

テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(haskell report) Traversableがわからない -> わかったかも

HaskellのTraversableの定義は以下. Traversableは, FunctorとFoldableの子供である(ギリシャ神話っぽい).

class (Functor t, Foldable t) => Traversable t where
    -- | Map each element of a structure to an action, evaluate
    -- these actions from left to right, and collect the results.
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

この型をよく見てみると, fmapの(a -> b) -> (t a -> t b)に似ていることが分かる. 仮に, fmapの中の出力型をApplicativeで包むと, Applicative f => (a -> f b) -> (t a -> f (t a))となる. なので, Traversableは, FunctorがFoldableの抽象化力に助けられて, 出力型をApplicativeにliftする力を得たと解釈出来る.

Applicativeは, 完全に文脈に閉じられた世界で関数を値に適用する能力を持つ(m (a -> b) -> m a -> m b). よって, 文脈の中でのfoldを強化する. だから, (a -> f b)をt aに適用して(ここでfmapを回収), t (f b)となった時に, foldしてf bを得ることが出来る.

従って, 私の理屈では, (a -> f b) -> (t a -> f b)ならば説明出来るのだが, 最後のtはどこかに行ってしまった. どこに行ったのだろうか・・.

(追記)

分かったかも知れない.

t (f a) -> f (t a)を得たいのであるが, の中で最初のtを抜かした, f a -> f (t a)に注目して, さらにfを外してみると, a -> t aとなる. 今, この関数sequenceAが再帰の形になるとすると, a -> t a -> t aがあれば, fはApplicativeより, f a -> f (t a) -> f (t a)が得られることになり, つまり, (謎の記法を使ってしまうけど),

sequenceA ":: f (t a)" = liftA2 ":: a -> t a -> t a" ":: f a" $ sequenceA "rest :: f (t a)"

という感じになり, foldの話に結びつけることが出来る. t (f a)をf aとt (f a)に分解出来ることがfoldそのものだから.

具体的には, fold (liftA2 ":: a -> t a -> t a" = :: f a -> f (t a) -> f (t a)) (init :: f (t a)) (xs :: t (f a))という形でfoldを使ってsequenceAを実現することが出来る.

拝承したっぽい.

(疑問)

sequenceAを実現するだけであれば, Functorは要らないのでは. どこで使ってるのだろうか?