Data.Traversable

Авторские права	Conor McBride и Ross Paterson 2005
Лицензия	BSD-стиль (см. файл LICENSE в дистрибутиве)
Поддержка	libraries@haskell.org
Стабильность	экспериментальная
Переносимость	переносимая
Безопасный Haskell	Достоверный
Язык	Haskell2010

Класс Traversable

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

Функторы, представляющие структуры данных, которые можно обходить слева направо.

Определение 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

(Закон естественности подразумевается параметричностью, а значит, подразумевается и закон чистоты [1, с. 15]).

Примеры аналогичны Functor, например, задан тип данных

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

подходящий экземпляр будет

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

Это подходит даже для абстрактных типов, так как законы для <*> подразумевают форму ассоциативности.

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

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

Ссылки: [1] Суть паттерна итератора, Jeremy Gibbons и Bruno C. d. S. Oliveira

Вспомогательные функции

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_.

mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) Источник

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

mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) Источник

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

Общие определения для методов суперкласса

fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b Источник

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

fmapDefault f ≡ runIdentity . traverse (Identity . f)

foldMapDefault :: forall t m a. (Traversable t, Monoid m) => (a -> m) -> t a -> m Источник

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

foldMapDefault f ≡ getConst . traverse (Const . f)