Haskell Language
가로 지르는

소개

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]]