Applicative
値をそのまま包むほか、二つの対象を結合し、それぞれの中身に関数を適用できる構造。
モナドから分岐能力を奪い、逐次実行のみとなった下位互換とみなすこともできる。そう言うと弱そうに見えるが、Applicativeにしかできないトリックはたくさんあり、実はモナドよりも奥が深い。特にFunListの応用例は必見だ。
haskellclass Functor f => Applicative f where
pure :: a -> f a
(<*>) :: f (a -> b) -> f a -> f b
liftA2 :: (a -> b -> c) -> f a -> f b -> f c
(*>) :: f a -> f b -> f b
(<*) :: f a -> f b -> f a
Const base / Control.Applicative
haskellnewtype Const a b = Const { getConst :: a }
instance Monoid a => Applicative (Const a) where
pure _ = Const mempty
Const a <*> Const b = Const (a <> b)
モノイドに幽霊パラメータを加えればApplicativeになる。自明すぎて使い道がなさそうに見えるが、
lensのゲッター/フォールドの動作に重要な役割を果たす。
ZipList base / Control.Applicative
repeatとzipWith。
haskellnewtype ZipList a = ZipList { getZipList :: [a] }
instance Applicative ZipList where
pure = ZipList . repeat
ZipList xs <*> ZipList ys = ZipList (zipWith id xs ys)
V2, V3, V4 linear
このような振る舞いのApplicativeは俗にジッピーと呼ばれ、発想はZipListと同じだ。要素数が固定されている場合モナドにもなり、
join が対角成分を取り出す操作になる。
モナドとしての性質はさほど重要ではないのでこちらで紹介する。
haskelldata V2 a = V2 a a
instance Applicative V2 where
pure a = V2 a a
V2 f g <*> V2 x y = V2 (f x) (g y)
instance Monad V2 where
V2 x y >>= k = let V2 p _ = k x
V2 _ q = k y
in V2 p q
Compose base / Data.Functor.Compose
STM (IO a)のように二つのモナドを重ねてもモナドにはならないが、Applicativeにはなる。
haskellnewtype Compose f g a = Compose { getCompose :: f (g a) }
instance (Applicative f, Applicative g) => Applicative (Compose f g) where
pure x = Compose (pure (pure x))
Compose f <*> Compose x = Compose (liftA2 (<*>) f x)
Product base / Data.Functor.Product
ネストさせるのではなく、並立させてもよい。
haskelldata Product f g a = Pair (f a) (g a)
instance (Applicative f, Applicative g) => Applicative (Product f g) where
pure x = Pair (pure x) (pure x)
Pair f g <*> Pair x y = Pair (f <*> x) (g <*> y)
Day kan-extensions / Data.Functor.Day
Productと似ているが、結果を一つにまとめるので扱いやすい(?)。型が異なる二種類の命令を表現するのに、
objectiveと組み合わせて使われたことがある。
圏論におけるDay convolutionと対応する。
haskelldata Day f g a = forall x y. Day (f x) (g y) (x -> y -> a)
instance (Applicative f, Applicative g) => Applicative (Day f g) where
pure x = Day (pure ()) (pure ()) (\_ _ -> x)
(Day fa fb u) <*> (Day gc gd v) =
Day ((,) <$> fa <*> gc) ((,) <$> fb <*> gd)
(\(a,c) (b,d) -> u a b (v c d))
FunList
MonadにならないApplicativeな構造の中でも一際異彩を放つのがこれだ。
haskelldata FunList a b t = Pure t
| a :< FunList a b (b -> t)
deriving Functor
infixr 6 :<
instance Applicative (FunList a b) where
pure = Pure
(a :< k) <*> t = a :< (flip <$> k <*> t)
Pure f <*> m = fmap f m
sell :: a -> FunList a b b
sell a = a :< Pure id
Traversableな値、たとえば
Bin (Bin (Tip 0) (Tip 1)) (Tip 2) に対して
traverse sell すると、その内容物をリストのように0 :< 1 :< 2 :< ... と列挙し、最後に
\x y z -> Bin (Bin (Tip x) (Tip y)) (Tip z) に相当する、元の構造を保ったまま復元する関数を返す。これを応用すれば、
木構造だろうと何だろうとお構い無しに、
任意のTraversableに対するソートという常識破りな真似ができる。
あまりにもトリッキーに思えるが、FunListと等価な構造
Bazaarが
lens内部で使われている。
haskellsort :: forall t a. (Traversable t, Ord a) => t a -> t a
sort = go where
go :: t a -> t a
go t = case iter $ traverse sell t of
(False, t') -> t'
(True, t') -> go t'
iter :: FunList a a r -> (Bool, r)
iter (Pure t) = (False, t)
iter (x :< y :< r)
| x > y = (True, snd (iter (x :< r)) y)
iter (x :< r) = ($x) <$> iter r
Permutator
計算が前の結果に依存しないということは、順番を並び替えてもよいということでもある。つまりアクションに優先順位をつけてソートをするという挙動も実現できるのだ。
haskelldata Permutator i f a where
Pure :: a -> Permutator i f a
Ap :: !i -> f a -> Permutator i f (a -> b) -> Permutator i f b
instance Functor (Permutator i f) where
fmap f (Pure a) = Pure (f a)
fmap f (Ap i x y) = Ap i x ((f .) <$> y)
instance Ord i => Applicative (Permutator i f) where
pure = Pure
Pure f <*> r = fmap f r
f <*> Pure a = fmap ($ a) f
r0@(Ap i f r) <*> s0@(Ap j g s)
| i <= j = Ap i f $ flip <$> r <*> s0
| otherwise = Ap j g $ flip (.) <$> s <*> r0
liftP :: i -> f a -> Permutator i f a
liftP i f = Ap i f (Pure id)
runPermutator :: Applicative f => Permutator i f a -> f a
runPermutator = go where
go (Pure a) = pure a
go (Ap _ f r) = flip id <$> f <*> runPermutator r
使い道はありそうな雰囲気がある。