Applicative
値をそのまま包むほか、二つの対象を結合し、それぞれの中身に関数を適用できる構造。モナドから分岐能力を奪い、逐次実行のみとなった下位互換とみなすこともできる。そう言うと弱そうに見えるが、Applicativeにしかできないトリックはたくさんあり、実はモナドよりも奥が深い。特にFunListの応用例は必見だ。 code:haskell
class 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
code:haskell
newtype 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。
code:haskell
newtype 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が対角成分を取り出す操作になる。モナドとしての性質はさほど重要ではないのでこちらで紹介する。 code:haskell
data 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にはなる。
code:haskell
newtype 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
ネストさせるのではなく、並立させてもよい。
code:haskell
data 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と対応する。 code:haskell
data 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な構造の中でも一際異彩を放つのがこれだ。
code:haskell
data 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内部で使われている。 code:haskell
sort :: 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
計算が前の結果に依存しないということは、順番を並び替えてもよいということでもある。つまりアクションに優先順位をつけてソートをするという挙動も実現できるのだ。
code:haskell
data 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
使い道はありそうな雰囲気がある。