Цель класса Traversable

Может ли кто-нибудь объяснить мне, какова цель класса Traversable?

Определение типа:

class (Functor t, Foldable t) => Traversable (t :: * -> *) where

Итак, Traversable - это Functor t и Foldable t.

Функция traverse является членом Traversable и имеет следующую подпись:

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Почему результат должен быть завернут в аппликативный? В чем смысл этого?

У меня есть следующий пример:

module ExercisesTraversable where

  import Test.QuickCheck (Arbitrary, arbitrary)
  import Test.QuickCheck.Checkers (quickBatch, eq, (=-=), EqProp)
  import Test.QuickCheck.Classes (traversable)

  type TI = []

  newtype IdentityT a = IdentityT a
    deriving (Eq, Ord, Show)

  instance Functor IdentityT where
    fmap f (IdentityT a) = IdentityT (f a)

  instance Foldable IdentityT where
    foldMap f (IdentityT a) = f a

  instance Traversable IdentityT where
    traverse f (IdentityT a) = IdentityT <$> f a

  instance Arbitrary a => Arbitrary (IdentityT a) where
    arbitrary = do
      a <- arbitrary
      return (IdentityT a)

  instance Eq a => EqProp (IdentityT a) where (=-=) = eq

  main = do
    let trigger = undefined :: TI (Int, Int, [Int])
    quickBatch (traversable trigger)

Посмотрим на реализацию traverse:

traverse f (IdentityT a) = IdentityT <$> f a

Тип результата приложения f a должен быть аппликативным, почему? Достаточно ли функтора?

Ответ 1

Identity - это немного плохой пример, так как он всегда содержит ровно одно значение. Вы правы - в этом случае ограничение Functor f было бы достаточно. Но ясно, что большинство пересечений не так структурно тривиальны.

Что делает traverse: он "посещает", в определенном порядке, все элементы в контейнере, выполняет некоторую операцию над ними и реконструирует структуру, как она была. Это более мощно, чем

Functor t, который также позволяет вам посещать/изменять все элементы и восстанавливать структуру, но только полностью независимые друг от друга (что позволяет выбрать произвольный порядок вычисления, возвращая thunk в структуру до любого элементов были (лениво) отображены вообще и т.д.).
Foldable t, который приносит элементы в линейном порядке, но не восстанавливает структуру. В принципе, Foldable - это просто класс контейнеров, который можно понизить до простого списка, о чем свидетельствует
```
toList :: Foldable t => t a -> [a]
```
... или к конкатенации любого моноидального типа, через
```
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
```
Здесь результаты операции для каждого элемента объединяются посредством операции моноида (или, если нет элементов, результат равен mempty).

В случае traverse ограничение Applicative f в основном поднимает это объединение моноида на что-то, в котором вы также можете восстановить структуру. Соответствие

mempty      ::   m
pure mempty :: f m

(<>)        ::   m ->   m ->   m
liftA2 (<>) :: f m -> f m -> f m

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

Ответ 2

Traversable в Haskell объединяет концепцию картирования над контейнером (получая взамен подобный контейнер) с концепцией внутреннего итератора, которая выполняет эффект для каждого элемента.

По сравнению с внешними итераторами внутренние итераторы ограничены тем, что мы не можем использовать значение, полученное для одного элемента, чтобы решить, что делать с другими элементами. Мы не можем сказать "mmmm, если операция возвращает 7 для некоторого элемента, запускайте ракеты при обработке следующего".

Этот тип "жестких" вычислений, который не может изменить курс, основанный на значениях, определенных в середине пути, представлен в Haskell с помощью Applicative typeclass. То, что причина Traversable (контейнеры) и Applicative (эффекты) идут рука об руку. Functor недостаточно, потому что он не обеспечивает способ объединения эффективных действий.

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

Ответ 3

Тип результата приложения f a должен быть аппликативным, почему? Достаточно ли функтора?

Это фантастический вопрос. Оригинальная McBride и Paterson выходит в другом направлении: она замечает, что многие вычисления применимы по своей природе (можно переписать с помощью pure и <*>). Затем он замечает, что определенные контейнеры, такие как [], допускают функцию этого типа:

 idist :: Applicative f => [f a] -> f [a]
 idist = ...

Теперь мы вызываем sequence в классе Traversable. Все хорошо и хорошо, но это помогает исследовать силу наших предположений, когда мы пишем абстракции. Что делать, если мы попытались построить прохожущую библиотеку без Applicative, используя только Functor? Что именно пойдет не так?

Продукты!

Для этого помогает прочитать статью Jaskelioff и Rypacek, которая пытается привязать структуры теории категорий, которые соответствуют аппликативным функторам и проходных контейнеров. Наиболее интересным свойством проходящих контейнеров является то, что они закрываются под конечными суммами и продуктами. Это отлично подходит для программирования Haskell, где огромное количество типов данных можно определить с помощью сумм и продуктов:

data WeirdSum a = ByList [a] | ByMaybe (Maybe a)

instance Traversable WeirdSum where
  traverse a2fb (ByList as) =
    ByList <$> traverse a2fb as
  traverse a2fb (ByMaybe maybeA) =
    ByMaybe <$> traverse a2fb maybeA

А, еще больше доказательств того, что нам не нужна вся сила аппликативного! Здесь мы используем fmap. Теперь конечные произведения:

data WeirdProduct a = WeirdProduct [a] (Maybe a)

instance Traversable WeirdProduct where
  traverse a2fb (WeirdProduct as aMaybe) =
    WeirdProduct <$> traverse a2fb as <*> traverse a2fb aMaybe

Здесь невозможно написать определение с помощью только функторов: fmap отлично подходит для сумм, но не дает нам возможности "склеивать" два разных функториальных значения. Только с <*> мы можем "закрыть" пересекающиеся контейнеры над конечными продуктами.

Это все хорошо и хорошо, но не хватает точности. Мы являемся свидетельством того, что Functor может быть плохим, но можем ли мы рассуждать с первых принципов, что Applicative - это именно то, что нам нужно, не больше и не меньше?

Теория категорий!

Эта проблема решена во второй половине работы газеты Jaskelioff и Rypacek. В категориальных терминах функтор T является проходящим, если он допускает семейство естественных преобразований

{ sequence | sequence : TFX -> FTX, any applicative F }

где каждое естественное преобразование является "естественным в F" и учитывает моноидальную структуру аппликативной функторной композиции "". Это последняя фраза, последняя кусочка жаргона, где важно иметь Applicative, а не Functor. С Applicative f мы можем склеить значения типа f a и f b, где мы либо действуем на них (a la foo <$> fa <*> fb, где foo :: a -> b -> c и fa, fb :: f a, f b), либо просто вставляем их в кортеж f (a, b). Это приводит к возникновению вышеупомянутой "моноидальной структуры"; нам нужно это, чтобы доказать, что пересекающиеся функторы замкнуты над конечными произведениями, как мы показали выше. Без аппликаций мы даже не могли начать говорить о взаимодействии функторов и продуктов! Если Hask является нашей категорией типов Haskell, то аппликативный способ - это просто назвать Hask -to- Hask endofunctors, которые "ведут себя хорошо" около (->) типов и типов продуктов.

Надеюсь, этот двухсторонний ответ, один в практическом программировании и один в категорическом foo-foo, дает небольшую интуицию относительно того, почему вы хотите, чтобы аппликативные функции говорили о проходимости. Я думаю, что часто обходные пути вводятся с элементами магии вокруг них, но они очень мотивированы практическими проблемами с прочными теоретическими основами. В других языковых экосистемах могут быть более простые в использовании итерационные шаблоны и библиотеки, но я люблю одну простоту и элегантность traverse и sequence.