Data.Traversable

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

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

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

Законы класса см. в разделе Законы в 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) Исходный код

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

forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b) Исходный код

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) и так далее.

Фактически, возможно разложить структуру traversable t a на её форму (также известную как основание) типа t () и список её элементов [a]. Исходную структуру можно надёжно восстановить из её основания и списка элементов.

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

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

Для Applicative функтора f и Traversable функтора t сигнатуры типов 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)

Когда термин traversable — это простая переменная или выражение, а монадическое действие для выполнения — это нетривиальный блок 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 аппликативным функтором, так как законы для (<*>) подразумевают требуемую ассоциативность.

Мы можем добавить явную, не по умолчанию, инстанцию 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 для прохода.

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

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

Поскольку та же самая структура дерева используется во всех трёх случаях, можно использовать оболочки coerce для одновременного предоставления всех трёх вариантов! Пользователю необходимо только обернуть корень дерева в соответствующую оболочку newtype для желаемого порядка прохода. Соответствующие определения инстанций показаны ниже (см. преобразование, если вы не знакомы с использованием 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.

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

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

Метод 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, пустое значение — [], а 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, а именно 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

Самым простым applicative functor является 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.

Applicative functors, которые пропускают изменяемое состояние через вычисление, являются интересным применением 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. В качестве части Applicative конструирования 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, или построены напрямую аналогичным образом.

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

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

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

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

Const a b не только содержит просто значение a, параметр b — всего лишь фиктивный тип, но когда у m есть экземпляр Monoid, Const m является functor'ом 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 @()

Для которого Applicative построение 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 фукнтора, мы сначала рассмотрим более простой аналог. Сначала определим тип Vec2 фиксированной ширины 2 элемента, чей 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 порождает 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, число элементов которых равно минимальной длине ZipLists 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, вышеуказанное сводится к довольно лаконичному определению транспонирования, где используется приведение типов для неявного обертывания и разворачивания 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», Jeremy Gibbons и Bruno Oliveira, в Mathematically-Structured Functional Programming, 2006, онлайн по адресу http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator.
• «Applicative Programming with Effects», Conor McBride и 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», Mauro Jaskelioff и Ondrej Rypacek, в Mathematically-Structured Functional Programming, 2012, онлайн по адресу http://arxiv.org/pdf/1202.2919.