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 (x <*> y) = t x <*> t y

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

  newtype Identity a = Identity a

  instance Functor Identity where
    fmap f (Identity x) = Identity (f x)

  instance Applicative Indentity where
    pure x = Identity x
    Identity f <*> Identity x = Identity (f x)

  newtype Compose f g a = Compose (f (g a))

  instance (Functor f, Functor g) => Functor (Compose f g) where
    fmap f (Compose x) = Compose (fmap (fmap f) x)

  instance (Applicative f, Applicative g) => Applicative (Compose f g) where
    pure x = Compose (pure (pure x))
    Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

(Закон природности подразумевается параметричностью.)

Примеры аналогичны 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).

Функции-утилиты

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 :: Traversable t => (a -> b) -> t a -> t b Источник

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

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

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