Data.Traversable

class (Functor t, Foldable t) => Traversable (t :: Type -> Type) where Исходный код

Функторы, представляющие структуры данных, которые могут быть преобразованы в структуры той же формы путем выполнения действия Applicative (или, следовательно, Monad) над каждым элементом слева направо.

Более подробное описание того, что означает та же форма, различных методов, способов построения обходов и примеров продвинутого использования можно найти в разделе Обзор (Overview) модуля Data.Traversable.

Законы класса см. в разделе Законы (Laws) модуля Data.Traversable.

>>> traverse Just [1,2,3,4]
Just [1,2,3,4]

>>> traverse id [Right 1, Right 2, Right 3, Right 4]
Right [1,2,3,4]

>>> traverse (const Nothing) [1,2,3,4]
Nothing

>>> traverse (\x -> if odd x then Just x else Nothing)  [1,2,3,4]
Nothing

>>> traverse id [Right 1, Right 2, Right 3, Right 4, Left 0]
Left 0

>>> sequenceA [Just 1, Just 2, Just 3]
Just [1,2,3]

>>> sequenceA [Right 1, Right 2, Right 3]
Right [1,2,3]

>>> sequenceA [Just 1, Just 2, Just 3, Nothing]
Nothing

>>> sequenceA [Right 1, Right 2, Right 3, Left 4]
Left 4

>>> sequence $ Right [1,2,3,4]
[Right 1,Right 2,Right 3,Right 4]

>>> sequence $ [Right 1,Right 2,Right 3,Right 4]
Right [1,2,3,4]

>>> sequence $ Left [1,2,3,4]
Left [1,2,3,4]

>>> sequence $ [Left 0, Right 1,Right 2,Right 3,Right 4]
Left 0

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b) Source

for — это traverse с переставленными аргументами. Версию, игнорирующую результаты, см. в for_.

forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b) Source

forM — это mapM с переставленными аргументами. Версию, игнорирующую результаты, см. в forM_.

forAccumM :: (Monad m, Traversable t) => s -> t a -> (s -> a -> m (s, b)) -> m (s, t b) Source

forAccumM — это mapAccumM с переставленными аргументами.

С версии: base-4.18.0.0

mapAccumL :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) Source

Функция mapAccumL ведет себя как комбинация fmap и foldl; она применяет функцию к каждому элементу структуры, передавая накапливаемый параметр слева направо, и возвращает конечное значение этого аккумулятора вместе с новой структурой.

Примеры

>>> mapAccumL (\a b -> (a + b, a)) 0 [1..10]
(55,[0,1,3,6,10,15,21,28,36,45])

>>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]
("012345",["0","01","012","0123","01234"])

mapAccumR :: Traversable t => (s -> a -> (s, b)) -> s -> t a -> (s, t b) Source

Функция mapAccumR ведет себя как комбинация fmap и foldr; она применяет функцию к каждому элементу структуры, передавая накапливаемый параметр справа налево, и возвращает конечное значение этого аккумулятора вместе с новой структурой.

Примеры

>>> mapAccumR (\a b -> (a + b, a)) 0 [1..10]
(55,[54,52,49,45,40,34,27,19,10,0])

>>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]
("054321",["05432","0543","054","05","0"])

mapAccumM :: (Monad m, Traversable t) => (s -> a -> m (s, b)) -> s -> t a -> m (s, t b) Source

Функция mapAccumM ведет себя как комбинация mapM и mapAccumL, которая обходит структуру, вычисляя действия и передавая накапливаемый параметр слева направо. Она возвращает конечное значение этого аккумулятора вместе с новой структурой. Аккумулятор часто используется для кэширования промежуточных результатов вычисления.

Примеры

>>> let expensiveDouble a = putStrLn ("Doubling " <> show a) >> pure (2 * a)
>>> :{
mapAccumM (\cache a -> case lookup a cache of
    Nothing -> expensiveDouble a >>= \double -> pure ((a, double):cache, double)
    Just double -> pure (cache, double)
    ) [] [1, 2, 3, 1, 2, 3]
:}
Doubling 1
Doubling 2
Doubling 3
([(3,6),(2,4),(1,2)],[2,4,6,2,4,6])

С версии: base-4.18.0.0

fmapDefault :: Traversable t => (a -> b) -> t a -> t b Source

Эта функция может использоваться в качестве значения для fmap в экземпляре Functor при условии, что определена traverse. (Использование fmapDefault с экземпляром Traversable, определенным только через sequenceA, приведет к бесконечной рекурсии.)

fmapDefault f ≡ runIdentity . traverse (Identity . f)

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m Source

Эта функция может использоваться в качестве значения для foldMap в экземпляре Foldable.

foldMapDefault f ≡ getConst . traverse (Const . f)

Структуры Traversable поддерживают поэлементное упорядочивание эффектов Applicative (и, следовательно, также эффектов Monad) для построения новых структур той же формы, что и исходная.

Чтобы проиллюстрировать, что понимается под той же формой: если входная структура представляет собой [a], каждая выходная структура представляет собой список [b] той же длины, что и входная. Если на входе Tree a, каждый выход Tree b имеет тот же граф промежуточных узлов и листьев. Аналогично, если на входе 2-кортеж (x, a), каждым выходом будет 2-кортеж (x, b) и так далее.

На самом деле возможно декомпозировать обходимую структуру t a на ее форму (также называемую spine) типа t () и список ее элементов [a]. Исходную структуру можно точно восстановить из ее основы (spine) и списка элементов.

Реализация экземпляра Traversable для заданной структуры естественным образом следует из ее типа; подробности см. в разделе Конструирование. Экземпляры должны удовлетворять законам, перечисленным в разделе «Законы». Разнообразие вариантов применения структур Traversable проистекает из множества возможных вариантов аппликативных эффектов. Некоторые примеры см. в разделе Расширенные обходы.

Каждая структура Traversable является одновременно и Functor, и Foldable, поскольку необходимые экземпляры можно реализовать через traverse, используя fmapDefault для fmap и foldMapDefault для foldMap. Прямые оптимизированные реализации этих методов суперкласса в некоторых случаях могут быть более эффективными.

Для аппликативного функтора f (Applicative) и обходимого функтора t (Traversable) сигнатуры типов traverse и fmap весьма похожи:

fmap     :: (a -> f b) -> t a -> t (f b)
traverse :: (a -> f b) -> t a -> f (t b)

Ключевое отличие заключается в том, что fmap создает структуру, чьи элементы (типа f b) являются отдельными эффектами, тогда как traverse создает совокупный эффект, возвращающий структуры типа t b.

Например, когда f — это монада IO, а t — это List, fmap возвращает список действий IO, тогда как traverse конструирует действие IO, результатом вычисления которого является список возвращаемых значений отдельных действий, выполненных слева направо.

traverse :: (a -> IO b) -> [a] -> IO [b]

Функция mapM является специализацией traverse для случая, когда f — это Monad. Для монад mapM более идиоматична, чем traverse. В остальном они в целом идентичны (хотя mapM может быть специально оптимизирована для монад и работать эффективнее, чем более общая traverse).

traverse :: (Applicative f, Traversable t) => (a -> f b) -> t a -> f (t b)
mapM     :: (Monad       m, Traversable t) => (a -> m b) -> t a -> m (t b)

Когда обходимый терм представляет собой простую переменную или выражение, а запускаемое монадическое действие является нетривиальным блоком do, более естественно писать действие последним. Эта идиома поддерживается функциями for, forM и forAccumM, которые представляют собой версии с переставленными аргументами для traverse, mapM и mapAccumM соответственно.

Методы traverse и mapM имеют аналоги в модуле Data.Foldable. Это traverse_ и mapM_, а также их варианты с переставленными аргументами for_ и forM_ соответственно. Тип результата — f (), они не возвращают обновленную структуру и могут использоваться для последовательного выполнения эффектов над всеми элементами структуры Traversable (любой Foldable) исключительно ради их побочных эффектов.

Если структура Traversable пуста, результатом является pure (). При возникновении короткого замыкания эффектов результат f () может, например, быть Nothing, если f — это Maybe, или Left e, когда это Either e.

Возможно, стоит отметить, что Maybe является не только потенциальным функтором Applicative для возвращаемого значения первого аргумента traverse, но и сам по себе является структурой Traversable с нулем или одним элементом. Удобная идиома для условного выполнения действия исключительно ради его эффектов над значением Just (и ничегонеделания в противном случае):

-- action :: Monad m => a -> m ()
-- mvalue :: Maybe a
mapM_ action mvalue -- :: m ()

что более кратко, чем:

maybe (return ()) action mvalue

Идиома mapM_ работает без изменений, если тип mvalue позже рефакторится из Maybe a в Either e a (при условии, что по-прежнему допустимо ничего не делать в случае Left).

Когда traverse или mapM применяется к пустой структуре ts (такой, для которой null ts равен True), возвращаемым значением является pure ts независимо от переданной функции g :: a -> f b. Применить функцию невозможно, поскольку нет значений типа a, однако ее тип определяет соответствующий экземпляр pure.

null ts ==> traverse g ts == pure ts

В противном случае, когда ts не пуста и хотя бы одно значение типа b получается из каждого f a, структуры t b имеют ту же форму (длина списка, граф узлов дерева, ...), что и входная структура t a, однако позиции, ранее занимаемые элементами типа a, теперь содержат элементы типа b.

Один обход может порождать одну, ноль или множество таких структур. Случай с нулем возникает, когда один из эффектов f a, упорядоченных в процессе обхода, не возвращает значений для замены. Случай со многими структурами возникает, когда один из упорядоченных эффектов возвращает несколько значений.

Функция traverse не выполняет выборочную фильтрацию элементов в результирующей структуре, в отличие от, например, mapMaybe.

>>> let incOdd n = if odd n then Just $ n + 1 else Nothing
>>> mapMaybe incOdd [1, 2, 3]
[2,4]
>>> traverse incOdd [1, 3, 5]
Just [2,4,6]
>>> traverse incOdd [1, 2, 3]
Nothing

В приведенных выше примерах с Maybe в качестве Applicative f мы видим, что количество структур t b, созданных с помощью traverse, может отличаться от единицы: оно равно нулю, когда результат по короткому замыканию превращается в Nothing. То же самое может произойти, когда f — это List и результат равен [], или f — это Either e и результат равен Left (x :: e), или, возможно, значение empty некоторого функтора Alternative.

Когда f — это, например, List, и отображение g :: a -> [b] возвращает более одного значения для некоторых входных данных a (и хотя бы одно для всех a), результат mapM g ts будет содержать несколько структур той же формы, что и ts:

List.length (mapM g ts) == List.product (fmap (List.length . g) ts)

Например:

>>> List.length $ mapM (\n -> [1..n]) [1..6]
720
>>> List.product $ List.length . (\n -> [1..n]) <$> [1..6]
720

Иными словами, обход с функцией g :: a -> [b] по входной структуре t a возвращает список [t b], длина которого равна произведению длин списков, возвращаемых функцией g для каждого элемента входной структуры! Отдельные элементы a структуры поочередно заменяются каждым элементом из g a:

>>> mapM (\n -> [1..n]) $ Just 3
[Just 1,Just 2,Just 3]
>>> mapM (\n -> [1..n]) [1..3]
[[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3]]

Если какой-либо элемент структуры t a отображается функцией g в пустой список, то весь совокупный результат пуст, поскольку отсутствует значение для заполнения одной из позиций выходной структуры:

>>> mapM (\n -> [1..n]) $ [0..6] -- [1..0] is empty
[]

Методы sequenceA и sequence полезны, когда у вас есть контейнер отложенных аппликативных или монадических эффектов, и вы хотите объединить их в один эффект, производящий ноль или более контейнеров с вычисленными значениями.

sequenceA :: (Applicative f, Traversable t) => t (f a) -> f (t a)
sequence  :: (Monad       m, Traversable t) => t (m a) -> m (t a)
sequenceA = traverse id -- default definition
sequence  = sequenceA   -- default definition

Когда монада m является IO, применение sequence к списку действий IO выполняет каждое из них по очереди, возвращая список результатов:

sequence [putStr "Hello ", putStrLn "World!"]
    = (\a b -> [a,b]) <$> putStr "Hello " <*> putStrLn "World!"
    = do u1 <- putStr "Hello "
         u2 <- putStrLn "World!"
         return [u1, u2]         -- In this case  [(), ()]

Для sequenceA недетерминированное поведение List проще всего увидеть на примере списка списков (элементов некоторого общего фиксированного типа). Результатом является декартово произведение всех подсписков:

>>> sequenceA [[0, 1, 2], [30, 40], [500]]
[[0,30,500],[0,40,500],[1,30,500],[1,40,500],[2,30,500],[2,40,500]]

Поскольку входной список состоит из трех элементов (подсписков), результатом является список троек (той же формы).

Метод traverse имеет реализацию по умолчанию через sequenceA:

traverse g = sequenceA . fmap g

но полагаться на эту реализацию по умолчанию не рекомендуется — для этого требуется, чтобы структура уже независимо являлась Functor. Определение sequenceA через traverse id намного проще, чем traverse, выраженная через композицию sequenceA и fmap. Экземпляры, как правило, должны реализовывать traverse явно. В некоторых случаях также имеет смысл реализовать специализированную функцию mapM.

Поскольку fmapDefault определена через traverse (чье определение по умолчанию через sequenceA использует fmap), нельзя использовать fmapDefault для определения экземпляра Functor, если экземпляр Traversable напрямую определяет только sequenceA.

Когда монада m — это Either или Maybe (более обобщенно — любой MonadPlus), рассматриваемый эффект заключается в преждевременном прерывании (коротком замыкании) результата при обнаружении Left или Nothing (в более общем случае — mzero).

>>> sequence [Just 1,Just 2,Just 3]
Just [1,2,3]
>>> sequence [Just 1,Nothing,Just 3]
Nothing
>>> sequence [Right 1,Right 2,Right 3]
Right [1,2,3]
>>> sequence [Right 1,Left "sorry",Right 3]
Left "sorry"

Результат sequence работает по принципу «всё или ничего»: либо структуры в точности той же формы, что и входные данные, либо вовсе ничего. Функция sequence не выполняет выборочную фильтрацию, в отличие от, например, catMaybes или rights:

>>> catMaybes [Just 1,Nothing,Just 3]
[1,3]
>>> rights [Right 1,Left "sorry",Right 3]
[1,3]

Определение экземпляра Traversable для бинарного дерева очень похоже на соответствующий экземпляр Functor для заданного типа данных:

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

каноническим экземпляром Functor будет

instance Functor Tree where
   fmap g Empty        = Empty
   fmap g (Leaf x)     = Leaf (g x)
   fmap g (Node l k r) = Node (fmap g l) (g k) (fmap g r)

каноническим экземпляром Traversable будет

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

Это определение работает для любого g :: a -> f b, где f является аппликативным функтором, поскольку законы для (<*>) подразумевают требуемую ассоциативность.

При желании мы можем добавить явный невиртуальный (non-default) метод mapM:

   mapM g Empty        = return Empty
   mapM g (Leaf x)     = Leaf <$> g x
   mapM g (Node l k r) = do
       ml <- mapM g l
       mk <- g k
       mr <- mapM g r
       return $ Node ml mk mr

См. раздел Конструирование ниже для более подробного рассмотрения общего случая, однако, как упоминалось в Обзоре выше, определения экземпляров обычно довольно просты, и все интересное поведение является результатом интересного выбора функтора Applicative для обхода.

Возможно, стоит отметить, что определенный выше обход дает центрированную (in-order) последовательность элементов. Если же вам требуется последовательность в прямом порядке (pre-order) (сначала родительский узел, затем дочерние) или в обратном порядке (post-order) (сначала дочерние узлы, затем родительский), вы можете определить экземпляр соответствующим образом:

inOrderNode :: Tree a -> a -> Tree a -> Tree a
inOrderNode l x r = Node l x r

preOrderNode :: a -> Tree a -> Tree a -> Tree a
preOrderNode x l r = Node l x r

postOrderNode :: Tree a -> Tree a -> a -> Tree a
postOrderNode l r x = Node l x r

-- Traversable instance with in-order traversal
instance Traversable Tree where
    traverse g t = case t of
        Empty      -> pure Empty
        Leaf x     -> Leaf <$> g x
        Node l x r -> inOrderNode <$> traverse g l <*> g x <*> traverse g r

-- Traversable instance with pre-order traversal
instance Traversable Tree where
    traverse g t = case t of
        Empty      -> pure Empty
        Leaf x     -> Leaf <$> g x
        Node l x r -> preOrderNode <$> g x <*> traverse g l <*> traverse g r

-- Traversable instance with post-order traversal
instance Traversable Tree where
    traverse g t = case t of
        Empty      -> pure Empty
        Leaf x     -> Leaf <$> g x
        Node l x r -> postOrderNode <$> traverse g l <*> traverse g r <*> g x

Поскольку во всех трех случаях используется одна и та же базовая структура Tree, можно использовать обертки newtype, чтобы сделать доступными все три варианта одновременно! Пользователю достаточно лишь обернуть корень дерева в соответствующий newtype для желаемого порядка обхода. Соответствующие определения экземпляров показаны ниже (см. раздел приведение (coercion), если вы не знакомы с использованием coerce в примерах кода):

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}

-- Default in-order traversal

import Data.Coerce (coerce)
import Data.Traversable

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
instance Functor  Tree where fmap    = fmapDefault
instance Foldable Tree where foldMap = foldMapDefault

instance Traversable Tree where
    traverse _ Empty = pure Empty
    traverse g (Leaf a) = Leaf <$> g a
    traverse g (Node l a r) = Node <$> traverse g l <*> g a <*> traverse g r

-- Optional pre-order traversal

newtype PreOrderTree a = PreOrderTree (Tree a)
instance Functor  PreOrderTree where fmap    = fmapDefault
instance Foldable PreOrderTree where foldMap = foldMapDefault

instance Traversable PreOrderTree where
    traverse _ (PreOrderTree Empty)        = pure $ preOrderEmpty
    traverse g (PreOrderTree (Leaf x))     = preOrderLeaf <$> g x
    traverse g (PreOrderTree (Node l x r)) = preOrderNode
        <$> g x
        <*> traverse g (coerce l)
        <*> traverse g (coerce r)

preOrderEmpty :: forall a. PreOrderTree a
preOrderEmpty = coerce (Empty @a)
preOrderLeaf :: forall a. a -> PreOrderTree a
preOrderLeaf = coerce (Leaf @a)
preOrderNode :: a -> PreOrderTree a -> PreOrderTree a -> PreOrderTree a
preOrderNode x l r = coerce (Node (coerce l) x (coerce r))

-- Optional post-order traversal

newtype PostOrderTree a = PostOrderTree (Tree a)
instance Functor  PostOrderTree where fmap    = fmapDefault
instance Foldable PostOrderTree where foldMap = foldMapDefault

instance Traversable PostOrderTree where
    traverse _ (PostOrderTree Empty)        = pure postOrderEmpty
    traverse g (PostOrderTree (Leaf x))     = postOrderLeaf <$> g x
    traverse g (PostOrderTree (Node l x r)) = postOrderNode
        <$> traverse g (coerce l)
        <*> traverse g (coerce r)
        <*> g x

postOrderEmpty :: forall a. PostOrderTree a
postOrderEmpty = coerce (Empty @a)
postOrderLeaf :: forall a. a -> PostOrderTree a
postOrderLeaf = coerce (Leaf @a)
postOrderNode :: PostOrderTree a -> PostOrderTree a -> a -> PostOrderTree a
postOrderNode l r x = coerce (Node (coerce l) x (coerce r))

С учетом вышесказанного, для примера дерева:

inOrder :: Tree Int
inOrder = Node (Node (Leaf 10) 3 (Leaf 20)) 5 (Leaf 42)

мы получаем:

import Data.Foldable (toList)
print $ toList inOrder
[10,3,20,5,42]

print $ toList (coerce inOrder :: PreOrderTree Int)
[5,3,10,20,42]

print $ toList (coerce inOrder :: PostOrderTree Int)
[10,20,3,42,5]

Обычно также определяются экземпляры для дополнительных распространенных классов типов, таких как Eq, Ord, Show и т. д.

Чтобы иметь возможность рассуждать о том, как эффекты заданного типа Applicative будут упорядочиваться в обобщенной структуре Traversable с помощью ее метода traversable и связанных с ним методов, полезно более внимательно изучить реализацию обобщенного метода traverse. Мы рассмотрим, как строятся обобщенные обходы, главным образом для того, чтобы уметь предсказывать их поведение с точки зрения пользователя, даже если вы не определяете собственные экземпляры Traversable.

Обходимые структуры t a собираются инкрементально из своих составных частей, например путем добавления отдельных элементов типа a в начало или в конец либо, в более общем случае, путем рекурсивного комбинирования меньших составных обходимых блоков, содержащих несколько таких элементов.

Как и в примере с деревом выше, объединяемые компоненты обычно собираются вместе подходящим конструктором, то есть функцией, принимающей два или более аргументов и возвращающей составное значение.

Метод traverse дополняет простое инкрементальное конструирование протягиванием эффектов Applicative некоторой функции g :: a -> f b.

Базовыми строительными блоками, которые мы будем использовать для моделирования конструирования traverse, является гипотетический набор элементарных функций, некоторые из которых могут иметь прямые аналоги в конкретных структурах Traversable. Например, конструктор (:) является аналогом prepend для списков или более общего combine.

empty :: t a               -- build an empty container
singleton :: a -> t a      -- build a one-element container
prepend :: a -> t a -> t a -- extend by prepending a new initial element
append  :: t a -> a -> t a -- extend by appending a new final element
combine :: a1 -> a2 -> ... -> an -> t a -- combine multiple inputs

• Пустая структура не содержит элементов типа a, поэтому применять g не к чему, но поскольку нам нужен результат типа f (t b), мы просто используем экземпляр pure для f, чтобы обернуть пустое значение типа t b:

  traverse _ (empty :: t a) = pure (empty :: t b)

  Для монады List значением empty является [], тогда как для Maybe это Nothing. Для Either e a мы имеем случай empty для каждого значения e:

  traverse _ (Left e :: Either e a) = pure $ (Left e :: Either e b)

• Одноэлементная структура содержит только один элемент типа a, и traverse может взять этот a, применить g :: a -> f b, получив f b, а затем применить к нему fmap singleton, получив требуемый f (t b):

  traverse g (singleton a) = fmap singleton $ g a

  Обратите внимание, что если f — это List, а g возвращает несколько значений, результатом будет список из нескольких одноэлементных значений t b!

  Поскольку Maybe и Either являются либо пустыми, либо одноэлементными, мы получаем

  traverse _ Nothing = pure Nothing
  traverse g (Just a) = Just <$> g a

  traverse _ (Left e) = pure (Left e)
  traverse g (Right a) = Right <$> g a

  Для List значение empty — это [], а singleton — это (:[]), поэтому мы имеем:

  traverse _ []  = pure []
  traverse g [a] = fmap (:[]) (g a)
                 = (:) <$> (g a) <*> traverse g []
                 = liftA2 (:) (g a) (traverse g [])

• Когда структура строится путем добавления еще одного элемента через prepend или append, обход сводится к:

  traverse g (prepend a t0) = prepend <$> (g a) <*> traverse g t0
                            = liftA2 prepend (g a) (traverse g t0)

  traverse g (append t0 a) = append <$> traverse g t0 <*> g a
                           = liftA2 append (traverse g t0) (g a)

  Происхождение комбинаторного произведения в случае, когда f — это List, теперь должно быть очевидным: когда traverse g t0 содержит n элементов, а g a содержит m элементов, недетерминированный экземпляр Applicative для List даст результат с m * n элементами.

• При объединении более крупных блоков мы снова используем (<*>) для комбинирования обходов компонентов. При этом простые элементы a отображаются в f b через g, а составные обходимые подструктуры преобразуются через traverse g:

  traverse g (combine a1 a2 ... an) =
      combine <$> t1 <*> t2 <*> ... <*> tn
    where
       t1 = g a1          -- if a1 fills a slot of type @a@
          = traverse g a1 -- if a1 is a traversable substructure
       ... ditto for the remaining constructor arguments ...

Приведенные выше определения упорядочивают эффекты Applicative функции f в ожидаемом порядке, формируя результат ожидаемой формы t.

Для списков это принимает вид:

traverse g [] = pure []
traverse g (x:xs) = liftA2 (:) (g a) (traverse g xs)

Фактическое определение traverse для списков представляет собой эквивалентную правую свертку для облегчения слияния списков.

traverse g = foldr (\x r -> liftA2 (:) (g x) r) (pure [])

В разделах ниже мы рассмотрим некоторые продвинутые варианты эффектов Applicative, приводящие к совершенно разным трансформациям структур Traversable.

Эти примеры охватывают реализации функций fmapDefault, foldMapDefault, mapAccumL и mapAccumR, иллюстрируя использование Identity, Const и эффектов Applicative с состоянием. Пример с ZipList иллюстрирует использование менее известного экземпляра Applicative для списков.

Это дополнительный материал, который не является обязательным для базового понимания структур Traversable. Если вы впервые знакомитесь со структурами Traversable, вы можете вернуться к нему позже.

В некоторых примерах используется продвинутая возможность Haskell, а именно приведение типов (coercion) с помощью newtype. Это сделано по двум причинам:

• Использование coerce позволяет избежать загромождения кода функциями, оборачивающими и разворачивающими термы newtype, которые во время выполнения неотличимы от базового значения. Приведение типов особенно удобно, когда в противном случае пришлось бы применять несколько конструкторов newtype к аргументам функции, а затем снимать несколько слоев тех же конструкторов с результата функции.
• Использование coerce позволяет генерировать более эффективный код за счет повторного использования исходного значения вместо выделения памяти для обернутого клона.

Если вы не знакомы с coerce, не беспокойтесь: это просто сокращение, которое, например, при наличии:

newtype Foo a = MkFoo { getFoo :: a }
newtype Bar a = MkBar { getBar :: a }
newtype Baz a = MkBaz { getBaz :: a }
f :: Baz Int -> Bar (Foo String)

позволяет написать:

x :: Int -> String
x = coerce f

вместо

x = getFoo . getBar . f . MkBaz

Простейшим аппликативным функтором является Identity, который просто оборачивает и разворачивает чистые значения и применение функций. Это позволяет нам определить fmapDefault:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
import Data.Coercible (coerce)

fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b
fmapDefault = coerce (traverse @t @Identity @a @b)

Использование приведения устраняет необходимость явного оборачивания и разворачивания термов с помощью Identity и runIdentity.

Как отмечалось в Обзоре, функцию fmapDefault можно использовать для определения необходимого экземпляра Functor структуры Traversable только тогда, когда метод traverse реализован явно. Если бы кроме этого метод traverse определялся через sequenceA и fmap, это привело бы к бесконечному циклу.

Аппликативные функторы, протягивающие изменяющееся состояние через вычисление, представляют собой интересный сценарий использования traverse. Функции mapAccumL и mapAccumR в этом модуле определены через подобные обходы.

Сначала мы определим упрощенную (не являющуюся трансформером монад) версию State, которая протягивает состояние s по цепочке вычислений слева направо. Ее оператор (<*>) передает входное состояние сначала левому аргументу, а затем результирующее состояние передается правому аргументу, который возвращает конечное состояние.

newtype StateL s a = StateL { runStateL :: s -> (s, a) }

instance Functor (StateL s) where
    fmap f (StateL kx) = StateL $ \ s ->
        let (s', x) = kx s in (s', f x)

instance Applicative (StateL s) where
    pure a = StateL $ \s -> (s, a)
    (StateL kf) <*> (StateL kx) = StateL $ \ s ->
        let { (s',  f) = kf s
            ; (s'', x) = kx s' } in (s'', f x)
    liftA2 f (StateL kx) (StateL ky) = StateL $ \ s ->
        let { (s',  x) = kx s
            ; (s'', y) = ky s' } in (s'', f x y)

С помощью StateL мы можем определить mapAccumL следующим образом:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
mapAccumL :: forall t s a b. Traversable t
          => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL g s ts = coerce (traverse @t @(StateL s) @a @b) (flip g) ts s

Использование приведения устраняет необходимость явно оборачивать и разворачивать термы newtype.

Тип flip g может быть приведен к a -> StateL b, что делает его пригодным для использования с traverse. В рамках аппликативного конструирования StateL (t b) обновления состояния будут протягиваться слева направо вдоль последовательности элементов t a.

Хотя mapAccumR имеет сигнатуру типа, идентичную mapAccumL, она отличается ожидаемым порядком вычисления эффектов, который должен происходить справа налево.

Для этого нам понадобится модифицированная структура управления StateR, которая протягивает состояние справа налево, передавая входное состояние своему правому аргументу, а затем используя полученное состояние в качестве входного для левого аргумента:

newtype StateR s a = StateR { runStateR :: s -> (s, a) }

instance Functor (StateR s) where
    fmap f (StateR kx) = StateR $ \s ->
        let (s', x) = kx s in (s', f x)

instance Applicative (StateR s) where
    pure a = StateR $ \s -> (s, a)
    (StateR kf) <*> (StateR kx) = StateR $ \ s ->
        let { (s',  x) = kx s
            ; (s'', f) = kf s' } in (s'', f x)
    liftA2 f (StateR kx) (StateR ky) = StateR $ \ s ->
        let { (s',  y) = ky s
            ; (s'', x) = kx s' } in (s'', f x y)

С помощью StateR мы можем определить mapAccumR следующим образом:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
mapAccumR :: forall t s a b. Traversable t
          => (s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumR g s0 ts = coerce (traverse @t @(StateR s) @a @b) (flip g) ts s0

Использование приведения устраняет необходимость явно оборачивать и разворачивать термы newtype.

Различные обходы с состоянием могут быть построены из mapAccumL и mapAccumR при подходящем выборе g или созданы напрямую аналогичным образом.

Функтор Const делает возможным применение traverse для свертывания входной структуры в результирующее значение без конструирования каких-либо выходных значений того же типа или формы.

Как отмечалось выше, ограничение суперкласса Foldable оправдано тем, что из traverse можно построить foldMap, foldr и т. д. Используемый здесь метод полезен сам по себе и рассматривается ниже.

Ключевая особенность сверток заключается в том, что они могут редуцировать входную структуру до итогового значения. Часто ни сама входная структура, ни ее видоизмененная копия больше не нужны после вычисления свертки, а благодаря слиянию списков входные данные могут даже не находиться в памяти целиком одновременно.

На первый взгляд метод traverse не кажется подходящим строительным блоком для сверток, поскольку его возвращаемое значение f (t b), по-видимому, сохраняет измененные копии входной структуры. Но присутствие t b в сигнатуре типа не обязательно означает, что термы типа t b действительно встроены в f (t b). Простейший способ исключить лишние термы — основать аппликативный функтор, используемый с traverse, на Const.

Мало того, что Const a b содержит только значение a, а параметр b является всего лишь фантомным типом, так еще и когда для m существует экземпляр Monoid, Const m является функтором Applicative:

import Data.Coerce (coerce)
newtype Const a b = Const { getConst :: a } deriving (Eq, Ord, Show) -- etc.
instance Functor (Const m) where fmap = const coerce
instance Monoid m => Applicative (Const m) where
   pure _   = Const mempty
   (<*>)    = coerce (mappend :: m -> m -> m)
   liftA2 _ = coerce (mappend :: m -> m -> m)

Использование приведения устраняет необходимость явно оборачивать и разворачивать термы newtype.

Таким образом, мы можем определить специализацию traverse:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
traverseC :: forall t a m. (Monoid m, Traversable t)
          => (a -> Const m ()) -> t a -> Const m (t ())
traverseC = traverse @t @(Const m) @a @()

Для которой аппликативное конструирование traverse приводит к:

null ts ==> traverseC g ts = Const mempty

traverseC g (prepend x xs) = Const (g x) <> traverseC g xs

Иными словами, это позволяет определить:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
foldMapDefault :: forall t a m. (Monoid m, Traversable t) => (a -> m) -> t a -> m
foldMapDefault = coerce (traverse @t @(Const m) @a @())

Чего достаточно для определения экземпляра суперкласса Foldable:

Использование приведения устраняет необходимость явно оборачивать и разворачивать термы newtype.

instance Traversable t => Foldable t where foldMap = foldMapDefault

Однако может быть полезно также напрямую определить варианты реализаций по умолчанию для foldr и foldl', построение которых требует чуть более сложного механизма:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}
import Data.Coerce (coerce)
import Data.Functor.Const (Const(..))
import Data.Semigroup (Dual(..), Endo(..))
import GHC.Exts (oneShot)

foldrDefault :: forall t a b. Traversable t
             => (a -> b -> b) -> b -> t a -> b
foldrDefault f z = \t ->
    coerce (traverse @t @(Const (Endo b)) @a @()) f t z

foldlDefault' :: forall t a b. Traversable t => (b -> a -> b) -> b -> t a -> b
foldlDefault' f z = \t ->
    coerce (traverse @t @(Const (Dual (Endo b))) @a @()) f' t z
  where
    f' :: a -> b -> b
    f' a = oneShot $ \ b -> b `seq` f b a

В приведенном выше коде мы используем Endo b Monoid и его Dual для композиции последовательности обновлений аккумулятора b -> b в порядке либо слева направо, либо справа налево.

Использование seq в определении foldlDefault' обеспечивает строгость аккумулятора.

Использование приведения устраняет необходимость явно оборачивать и разворачивать термы newtype.

Функция oneShot дает компилятору подсказку, способствующую правильной оптимизации лямбда-термов, которые вызываются не более одного раза (для каждого элемента a), поэтому ему не следует пытаться предварительно вычислять и повторно использовать подвыражения, окупающиеся только при многократном выполнении. В остальном это просто функция тождества.

В качестве разминки перед рассмотрением аппликативного функтора ZipList Applicative мы сначала рассмотрим более простой аналог. Сначала определим тип 2-элементного вектора фиксированной длины Vec2, чей экземпляр Applicative объединяет пару функций с парой значений путем применения каждой функции к соответствующей позиции значения:

data Vec2 a = Vec2 a a
instance Functor Vec2 where
    fmap f (Vec2 a b) = Vec2 (f a) (f b)
instance Applicative Vec2 where
    pure x = Vec2 x x
    liftA2 f (Vec2 a b) (Vec2 p q) = Vec2 (f a p) (f b q)
instance Foldable Vec2 where
    foldr f z (Vec2 a b) = f a (f b z)
    foldMap f (Vec2 a b) = f a <> f b
instance Traversable Vec2 where
    traverse f (Vec2 a b) = Vec2 <$> f a <*> f b

Наряду с аналогичным определением для 3-элементных векторов фиксированной длины:

data Vec3 a = Vec3 a a a
instance Functor Vec3 where
    fmap f (Vec3 x y z) = Vec3 (f x) (f y) (f z)
instance Applicative Vec3 where
    pure x = Vec3 x x x
    liftA2 f (Vec3 p q r) (Vec3 x y z) = Vec3 (f p x) (f q y) (f r z)
instance Foldable Vec3 where
    foldr f z (Vec3 a b c) = f a (f b (f c z))
    foldMap f (Vec3 a b c) = f a <> f b <> f c
instance Traversable Vec3 where
    traverse f (Vec3 a b c) = Vec3 <$> f a <*> f b <*> f c

С приведенными выше определениями функция sequenceA (как и traverse id) действует как операция транспонирования матрицы на Vec2 (Vec3 Int), давая соответствующий Vec3 (Vec2 Int):

Пусть t = Vec2 (Vec3 1 2 3) (Vec3 4 5 6) — наша структура Traversable, а g = id :: Vec3 Int -> Vec3 Int — функция, используемая для обхода t. Тогда мы имеем:

traverse g t = Vec2 <$> (Vec3 1 2 3) <*> (Vec3 4 5 6)
             = Vec3 (Vec2 1 4) (Vec2 2 5) (Vec2 3 6)

Эту конструкцию можно обобщить с векторов фиксированной длины на списки переменной длины с помощью ZipList. Это дает операцию транспонирования, которая хорошо работает для списков равной длины. Если некоторые из списков длиннее других, они усекаются до наибольшей общей длины.

Мы уже рассматривали стандартный экземпляр Applicative для List, для которого применение m функций f1, f2, ..., fm к n входным значениям a1, a2, ..., an дает m * n результатов:

>>> :set -XTupleSections
>>> [("f1",), ("f2",), ("f3",)] <*> [1,2]
[("f1",1),("f1",2),("f2",1),("f2",2),("f3",1),("f3",2)]

Однако существуют еще два распространенных способа превратить списки в управляющие структуры Applicative. Первый — через Const [a], поскольку списки являются моноидами относительно конкатенации, а мы уже видели, что Const m является функтором Applicative, когда m — это Monoid. Второй основан на zipWith и называется ZipList:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}
newtype ZipList a = ZipList { getZipList :: [a] }
    deriving (Show, Eq, ..., Functor)

instance Applicative ZipList where
    liftA2 f (ZipList xs) (ZipList ys) = ZipList $ zipWith f xs ys
    pure x = repeat x

Определение liftA2 достаточно понятно: вместо применения f к каждой паре (x, y), независимо выбираемой из xs и ys, используются только соответствующие пары по каждому индексу в двух списках.

Определение pure может показаться неожиданным, но оно необходимо для соблюдения законов экземпляра:

liftA2 f (pure x) ys == fmap (f x) ys

Поскольку ys может иметь любую длину, нам необходимо предоставить бесконечный запас значений x в pure x, чтобы иметь значение для сопоставления в пару с каждым элементом y.

Когда ZipList выступает в роли функтора Applicative, используемого при конструировании обхода, ZipList, содержащий частично построенную структуру с m элементами, объединяется с компонентом, содержащим n элементов, через zipWith, в результате чего получается min m n результатов!

Следовательно, traverse с g :: a -> ZipList b сформирует ZipList структур t b, количество элементов в которых равно минимальной длине списков ZipList g a, где a пробегает элементы t. Когда t пусто, длина бесконечна (как и ожидается для минимума пустого множества).

Если структура t содержит значения типа ZipList a, мы можем использовать функцию тождества id :: ZipList a -> ZipList a в качестве первого аргумента traverse:

traverse (id :: ZipList a -> ZipList a) :: t (ZipList a) -> ZipList (t a)

Количество элементов в результирующем ZipList будет равно длине кратчайшего элемента-ZipList в t. Каждый выходной t a будет иметь ту же форму, что и входной t (ZipList a), то есть содержать то же количество элементов.

Если представить элементы t (ZipList a) как его строки, а элементы каждого отдельного ZipList как столбцы этой строки, мы увидим, что наш обход реализует операцию транспонирования, меняющую местами строки и столбцы t после предварительного усечения всех строк до количества столбцов в самой короткой из них.

Поскольку на самом деле traverse id — это просто sequenceA, вышесказанное сводится к весьма лаконичному определению функции transpose, где приведение используется для неявного оборачивания и разворачивания ZipList newtype по мере необходимости, давая функцию, работающую со списком списков:

>>> :set -XScopedTypeVariables
>>> import Control.Applicative (ZipList(..))
>>> import Data.Coerce (coerce)
>>> >>> :{
>>> let
>>>     transpose :: forall a. [[a]] -> [[a]]
>>>     transpose = coerce (sequenceA :: [ZipList a] -> ZipList [a])
>>> in transpose [[1,2,3],[4..],[7..]]
>>> :}
[[1,4,7],[2,5,8],[3,6,9]]

Использование приведения устраняет необходимость явно оборачивать и разворачивать термы ZipList.

Определение traverse должно удовлетворять следующим законам:

Естественность

t . traverse f = traverse (t . f) для каждого аппликативного преобразования t

Тождественность

traverse Identity = Identity

Композиция

traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

Определение sequenceA должно удовлетворять следующим законам:

Естественность

t . sequenceA = sequenceA . fmap t для каждого аппликативного преобразования t

Тождественность

sequenceA . fmap Identity = Identity

Композиция

sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

где аппликативное преобразование — это функция

t :: (Applicative f, Applicative g) => f a -> g a

сохраняющая операции Applicative, то есть

t (pure x) = pure x
t (f <*> x) = t f <*> t x

а функтор тождества Identity и функторы композиции Compose взяты из Data.Functor.Identity и Data.Functor.Compose.

Следствием закона естественности является закон чистоты для traverse

traverse pure = pure

Экземпляры суперклассов должны удовлетворять следующему:

• В экземпляре Functor метод fmap должен быть эквивалентен обходу с аппликативным функтором тождества (fmapDefault).
• В экземпляре Foldable метод foldMap должен быть эквивалентен обходу с константным аппликативным функтором (foldMapDefault).

Примечание: суперкласс Functor означает, что (в GHC) обходимые (Traversable) структуры не могут накладывать никаких ограничений на тип элемента. Реализация Haskell с поддержкой функторов с ограничениями могла бы сделать возможным определение структур Traversable с ограничениями.

• "The Essence of the Iterator Pattern", by Jeremy Gibbons and Bruno Oliveira, in Mathematically-Structured Functional Programming, 2006, онлайн по адресу http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator.
• "Applicative Programming with Effects", by Conor McBride and Ross Paterson, Journal of Functional Programming 18:1 (2008) 1-13, онлайн по адресу http://www.soi.city.ac.uk/~ross/papers/Applicative.html.
• "An Investigation of the Laws of Traversals", by Mauro Jaskelioff and Ondrej Rypacek, in Mathematically-Structured Functional Programming, 2012, онлайн по адресу http://arxiv.org/pdf/1202.2919.