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 определяется путем выполнения traverse в аппликативном fmapDefault Identity .

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 , который игнорирует его параметр при накоплении моноидального значения.

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 обычно выглядят как реализация fmap в Applicative контексте.

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 аппликативного функтора , который переворачивает существующий аппликативный так, чтобы скомпонованные эффекты имели место в обратном порядке.

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 новый тип найден в разделе 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 s.

Преобразование структуры с пересечением с помощью накопительного параметра

Две функции 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 в обратном порядке .

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 и 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 structure для развертывания sequenceA как своего рода n-ary zip , скрепляя вместе все внутренние списки вместе поточечно.

[] умолчанию «приоритетный выбор». Applicative экземпляр не подходит для нашего использования - нам нужен «zippy» Applicative . Для этого мы используем ZipList , который находится в Control.Applicative .

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

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

Теперь мы получаем transpose бесплатно, ZipList в ZipList 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]]