• Data.Foldable
• Data.Traversable

lensFold,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.

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"


## 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.

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が正の位置と負の位置両方に出てくるので関手ではない

また、SetOrd制約のためFunctorにできない

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

### FoldableであるがTraversableでない例

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

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