Haskell Language
トラバーサブル

前書き

トラバーサブル構造のためのファンクタのインスタンス化と折りたたみ

import Data.Traversable as Traversable

data MyType a =  -- ...
instance Traversable MyType where
    traverse = -- ...

すべてのTraversable構造を作製することができるFoldable Functor使用fmapDefaultとfoldMapDefaultで見つかった機能Data.Traversable 。

instance Functor MyType where
    fmap = Traversable.fmapDefault

instance Foldable MyType where
    foldMap = Traversable.foldMapDefault

fmapDefaultは、 Identityアプリケーションファンクタでtraverseを実行traverseによって定義されます。

newtype Identity a = Identity { runIdentity :: a }

instance Applicative Identity where
    pure = Identity
    Identity f <*> Identity x = Identity (f x)

fmapDefault :: Traversable t => (a -> b) -> t a -> t b
fmapDefault f = runIdentity . traverse (Identity . f)

foldMapDefaultは、 Const適用ファンクタを使用して定義されます。このfoldMapDefaultは、単項式値を累積しながらそのパラメータを無視します。

newtype Const c a = Const { getConst :: c }

instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = getConst . traverse (Const . f)

バイナリツリーのTraversableのインスタンス

traverse実装は、通常、 Applicativeコンテキストに持ち上げられたfmap実装のように見えます。

data Tree a = Leaf
            | Node (Tree a) a (Tree a)

instance Traversable Tree where
    traverse f Leaf = pure Leaf
    traverse f (Node l x r) = Node <$> traverse f l <*> f x <*> traverse f r

この実装は、ツリーの順序通りのトラバーサルを実行します。

ghci> let myTree = Node (Node Leaf 'a' Leaf) 'b' (Node Leaf 'c' Leaf)

--    +--'b'--+
--    |       |
-- +-'a'-+ +-'c'-+
-- |     | |     |
-- *     * *     *

ghci> traverse print myTree
'a'
'b'
'c'

DeriveTraversable拡張により、GHCは型の構造に基づいてTraversableインスタンスを生成することができます。 Nodeコンストラクタのレイアウトを調整することで、機械で書かれたトラバーサルの順序を変えることができます。

data Inorder a = ILeaf
               | INode (Inorder a) a (Inorder a)  -- as before
               deriving (Functor, Foldable, Traversable)  -- also using DeriveFunctor and DeriveFoldable

data Preorder a = PrLeaf
                | PrNode a (Preorder a) (Preorder a)
                deriving (Functor, Foldable, Traversable)

data Postorder a = PoLeaf
                 | PoNode (Postorder a) (Postorder a) a
                 deriving (Functor, Foldable, Traversable)

-- injections from the earlier Tree type
inorder :: Tree a -> Inorder a
inorder Leaf = ILeaf
inorder (Node l x r) = INode (inorder l) x (inorder r)

preorder :: Tree a -> Preorder a
preorder Leaf = PrLeaf
preorder (Node l x r) = PrNode x (preorder l) (preorder r)

postorder :: Tree a -> Postorder a
postorder Leaf = PoLeaf
postorder (Node l x r) = PoNode (postorder l) (postorder r) x

ghci> traverse print (inorder myTree)
'a'
'b'
'c'
ghci> traverse print (preorder myTree)
'b'
'a'
'c'
ghci> traverse print (postorder myTree)
'a'
'c'
'b'

逆の構造を横切る

トラバーサルは、の助けを借りて反対方向に実行することができますBackwardsのApplicativeファンクタ構成の効果は逆の順序で行われるように、既存の応用的に反転させ、。

newtype Backwards f a = Backwards { forwards :: f a }

instance Applicative f => Applicative (Backwards f) where
    pure = Backwards . pure
    Backwards ff <*> Backwards fx = Backwards ((\x f -> f x) <$> fx <*> ff)

Backwards 「を逆に使用するために置くことができるtraverse 」。 traverseコールの基礎となるアプリケーションがBackwardsで反転されると、その結果は逆の順序で発生します。

newtype Reverse t a = Reverse { getReverse :: t a }

instance Traversable t => Traversable (Reverse t) where
    traverse f = fmap Reverse . forwards . traverse (Backwards . f) . getReverse

ghci> traverse print (Reverse "abc")
'c'
'b'
'a'

Reverse newtypeは、Data.Functor.Reverseの下にあります。

トラバーサブルの定義

class (Functor t, Foldable t) => Traversable t where
    {-# MINIMAL traverse | sequenceA #-}
    
    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse f = sequenceA . fmap f
    
    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id
    
    mapM :: Monad m => (a -> m b) -> t a -> m (t b)
    mapM = traverse
    
    sequence :: Monad m => t (m a) -> m (t a)
    sequence = sequenceA

Traversable構造tある有限演算コンテナ要素の副作用の「訪問者」操作でオン動作させることができます。 aビジター関数f :: a -> fbは構造体の各要素に副作用を行い、 traverse Applicativeを使って副作用を構成しApplicative 。それを見るもう1つの方法は、 sequenceAは、 Traversable構造がApplicative通勤すると言います。

累積パラメータを使用してトラバーサル構造を変換する

2つのmapAccum関数は、フォールディングとマッピングの操作を結合します。

--                                                       A Traversable structure
--                                                                   |
--                                                     A seed value  |
--                                                             |     |
--                                                            |-|  |---|
mapAccumL, mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
--                                      |------------------|              |--------|
--                                               |                            |
--                       A folding function which produces a new mapped       |
--                         element 'c' and a new accumulator value 'a'        |
--                                                                            |
--                                                            Final accumulator value
--                                                             and mapped structure

これらの関数は、マップされた値が折り畳まれたときに以前に起こったことに依存することを可能にするという点でfmapを一般化しています。彼らはfoldl / foldrを一般化し、構造体を適切な位置にマッピングするだけでなく、値を減らすという点で一般化します。

例えば、 tails使用して実装することができmapAccumR 、その妹はinits使用して実装することができmapAccumL 。

tails, inits :: [a] -> [[a]]
tails = uncurry (:) . mapAccumR (\xs x -> (x:xs, xs)) []
inits = uncurry snoc . mapAccumL (\xs x -> (x `snoc` xs, xs)) []
    where snoc x xs = xs ++ [x]

ghci> tails "abc"
["abc", "bc", "c", ""]
ghci> inits "abc"
["", "a", "ab", "abc"]

mapAccumLは、 Stateアプリケーションファンクタをトラバースすることによって実装されます。

{-# LANGUAGE DeriveFunctor #-}

newtype State s a = State { runState :: s -> (s, a) } deriving Functor
instance Applicative (State s) where
    pure x = State $ \s -> (s, x)
    State ff <*> State fx = State $ \s -> let (t, f) = ff s
                                              (u, x) = fx t
                                          in (u, f x)

mapAccumL f z t = runState (traverse (State . flip f) t) z

mapAccumR mapAccumL を逆に実行することでmapAccumL します 。

mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse

コンテンツを持つ形状としてのトラバース可能な構造

タイプtがTraversable場合、 ta値は2つの部分に分けることができます：その "形状"と "内容"：

data Traversed t a = Traversed { shape :: t (), contents :: [a] }

「コンテンツ」はFoldableインスタンスを使用して「訪問する」ものと同じです。

taからTraversed ta向かう一方向にはFunctorとFoldable以外何も必要ありません

break :: (Functor t, Foldable t) => t a -> Traversed t a 
break ta = Traversed (fmap (const ()) ta) (toList ta)

しかし、戻ってくることは、 traverse機能を決定的に使う

import Control.Monad.State

-- invariant: state is non-empty
pop :: State [a] a
pop = state $ \(a:as) -> (a, as)

recombine :: Traversable t => Traversed t a -> t a
recombine (Traversed s c) = evalState (traverse (const pop) s) c

Traversable法では、 break . recombine必要ですbreak . recombine 、 recombine . breakは両方ともアイデンティティです。特に、これはcontentsに完全なshape完全に残すことなく残しておくために正しい数の要素が正確に存在することを意味します。

Traversed tはTraversed t Traversableです。 traverseの実装は、リストのTraversableのインスタンスを使用して要素を訪問し、不活性形状を結果に再接続することによって機能します。

instance Traversable (Traversed t) where
    traverse f (Traversed s c) = fmap (Traversed s) (traverse f c)

リストの並び替え

そのzipがタプルのリストをタプルのリストに入れ替えることに注目して、

ghci> uncurry zip ([1,2],[3,4])
[(1,3), (2,4)]

およびtransposeのタイプとsequenceA間の類似性、

-- transpose exchanges the inner list with the outer list
--           +---+-->--+-+
--           |   |     | |
transpose :: [[a]] -> [[a]]
--            | |     |   |
--            +-+-->--+---+

-- sequenceA exchanges the inner Applicative with the outer Traversable
--                                             +------>------+
--                                             |             |
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
--                                                |       |
--                                                +--->---+

考え方は[]のTraversable and Applicative構造を使用してsequenceAをn-ary zip一種として展開し、すべての内部リストをポイントワイズに一緒に圧縮することです。

[]のデフォルトの "優先順位付けされた選択" Applicativeインスタンスは私たちの使用には適切ではありません - "zippy" Applicativeが必要です。このために、 Control.ApplicativeあるZipList newtypeを使用します。

newtype ZipList a = ZipList { getZipList :: [a] }

instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith ($) fs xs)

今度は、 ZipList Applicativeをトラバースして、無料でtransposeしApplicative 。

transpose :: [[a]] -> [[a]]
transpose = getZipList . traverse ZipList

ghci> let myMatrix = [[1,2,3],[4,5,6],[7,8,9]]
ghci> transpose myMatrix
[[1,4,7],[2,5,8],[3,6,9]]