Haskell Language
トラバーサブル
サーチ…
前書き
Traversable
クラスは、以前はmapM :: Monad m => (a -> mb) -> [a] -> m [b]
として知られている関数を一般化し、リスト以外の構造に対してApplicative
効果をmapM :: Monad m => (a -> mb) -> [a] -> m [b]
ます。
トラバーサブル構造のためのファンクタのインスタンス化と折りたたみ
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]]