Haskell Language
가로 지르는
수색…
소개
Traversable
클래스는 이전에 mapM :: Monad m => (a -> mb) -> [a] -> m [b]
로 알려진 함수를 일반화하여 목록 이외의 구조에 Applicative
효과를 Applicative
합니다.
Traversable 구조체를위한 Functor 및 Foldable 인스턴스화
import Data.Traversable as Traversable
data MyType a = -- ...
instance Traversable MyType where
traverse = -- ...
모든 Traversable
구조는 이루어질 수 Foldable
Functor
은 USING fmapDefault
및 foldMapDefault
검색된 기능 Data.Traversable
.
instance Functor MyType where
fmap = Traversable.fmapDefault
instance Foldable MyType where
foldMap = Traversable.foldMapDefault
fmapDefault
는 Identity
applicative functor에서 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
applicative functor를 사용하여 정의되며, monoidal 값을 누적하면서 매개 변수를 무시합니다.
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
applicator 는 기존 응용 프로그램을 뒤집어서 구성된 효과가 역순으로 발생하도록합니다.
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 아래에 있습니다.
Traversable의 정의
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
사용하여 부작용을 구성합니다. 그것을 보는 또 다른 방법은 sequenceA
가 Traversable
구조가 Applicative
와 통학한다고 말합니다.
누적 매개 변수를 사용하여 Traversable 구조 변환
두 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
applicator에서 횡단하여 구현됩니다.
{-# 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
을 반대로 실행하여 작동합니다.
mapAccumR f z = fmap getReverse . mapAccumL f z . Reverse
내용이있는 형태의 이동식 구조
타입 t
가 Traversable
경우, ta
값은 두 개의 부분으로 나눌 수 있습니다 : "모양"과 "내용":
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
는 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
인스턴스는 우리의 사용하기에 적합하지 않습니다 - 우리가 "기운찬"필요 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
합니다.
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]]