• Data.Foldable
  • Data.Traversable

lensのFold,Traversalの、前提を(私が)理解するために書かれた記事

Foldable

class Foldable t where
    foldMap :: Monoid m => (a -> m) -> t a -> m
    foldr :: (a -> b -> b) -> b -> t a -> b
-- Minimal complete definition: foldMap or foldr.

Class of data structures that can be folded to a summary value.

畳み込んで一点に潰す演算の可能な型クラス。Prelude.foldrの一般化。満たすべき制約はない。

具体例をコードで示す。

instance Foldable [] where
    foldMap _ [] = mempty
    foldMap f (x : xs) = f x <> foldMap xs

instance Foldable Maybe where
    foldMap _ Nothing  = mempty
    foldMap f (Just x) = f x

instance Foldable Identity where
    foldMap f (Identity x) = f x

data Tree a = Leaf a | Tree (Tree a) (Tree a)
instance Foldable Tree where
    foldMap f (Leaf x) = f x
    foldMap f (Tree l r) = foldMap f l <> foldMap f r

>>> foldMap show (Tree (Tree (Leaf 18) (Leaf 19)) (Leaf 20))
"181920"

他にEither a,(,) a,Proxy *,Const aもinstanceである。baseに限ると今挙げたもので全てである。

Traversable

class (Functor t, Foldable t) => Traversable t where
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)
-- Minimal complete definition: traverse or sequenceA.

Class of data structures that can be traversed from left to right, performing an action on each element.

左から右へなめて作用を各点ごとに評価可能な型クラス。Prelude.sequenceの一般化。構造を保つことが期待される。

instance Traversable [] where
    traverse f [] = pure []
    traverse f (x:xs) = (:) <$> f x <*> traverse f xs

instance Traversable Maybe where
    traverse f Nothing = pure Nothing
    traverse f (Just x) = Just <$> f x

instance Traversable Identity where
    traverse f (Identity x) = Identity <$> f x

data Tree a = Leaf a | Tree (Tree a) (Tree a)
instance Traversable Tree where
    traverse f (Leaf x) = Leaf <$> f x
    traverse f (Tree l r) = Tree <$> traverse f l <*> traverse f r

>>> traverse (\ n -> print n >> return (n ^ 2)) (Tree (Tree (Leaf 18) (Leaf 19)) (Leaf 20))
18
19
20
Tree (Tree (Leaf 324) (Leaf 361)) (Leaf 400)

上で挙げたFoldableのinstanceは全てTraversableでもある。

制約

traverseは構造を保たなければならない。

identity

traverse Identity = Identity

naturality

t . traverse f = traverse (t . f) -- for every applicative transformation t

ただしtは-XRank2Typesを有効にし明示的に全称量化すること

型内訳

Applicative f
Traversable t
a, b
t :: forall x y. f x -> f y
f :: a -> f b

舐めてからmapしても舐めるときにmapしても同じ

composition

traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

ただしComposeは関手の合成

newtype Compose f g a = Compose (f (g a))
instance (Traversable f, Traversable g) => Traversable (Compose f g)

Applicative f, g
Traversable t
a, b, c
f :: a -> f b
g :: b -> g c

まとめて舐めても一段ずつ舐めても同じ

関係

Traversableからのdefault実装

  • TraversableならFunctor
  • TraversableならFoldable

それぞれfmapDefault, foldMapDefaultという名前で実装が与えられており、Traversableのinstanceを書けばfmap, foldMapは与えられる。

fmapDefault    f = runIdentity . traverse (Identity . f)
foldMapDefault f = getConst    . traverse (Const    . f)

FoldableであるがFunctorでない例

data Iter a = Iter (a -> a) a

instance Foldable Iter where
    foldMap f (Iter g a) = mconcat . map f $ iterate g a

a -> aという形でaが正の位置と負の位置両方に出てくるので関手ではない

また、SetもOrd制約のためFunctorにできない

Haskell : An example of a Foldable which is not a Functor (or not Traversable)? - Stack Overflow

FoldableであるがTraversableでない例

SetはOrdを抜きにしてもTraversableでない。mapの結果同じ要素ができて潰れると構造が変化してしまうためである。

[Haskell-cafe] Non-traversable foldables - Google グループ

参考

記述時のbaseは4.7.0.1