Что означает Traversable для аппликативного контекста? - PullRequest
Новая
       69

Что означает Traversable для аппликативного контекста?

7 голосов
/ 05 апреля 2019

Я пытаюсь понять Traversable с помощью https://namc.in/2018-02-05-foldables-traversals.

Где-то автор упомянул следующее предложение:

Traversable для контекстов Applicative, что такое FoldableМоноидные значения.

Что он пытался уточнить?

У меня нет связи между Foldable to Monoid.

Пожалуйста, приведите пример.

Ответы [ 2 ]

8 голосов
/ 05 апреля 2019

В начале было foldr: 

foldr :: (a -> b -> b) -> b -> [a] -> b

и было mapM: 

mapM :: Monad m => (a -> m b) -> [a] -> m [b]

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

-- old foldr ::        (a -> b -> b) -> b -> [] a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t  a -> b

Если у вас есть моноид, вам не нужно указывать двоичную функцию, потому что экземпляр Monoid уже предоставляет свое собственное начальное значение и знает, как объединить два значения, что очевидно из определения по умолчанию в терминах foldr 

-- If m is a monoid, it provides its own function of type b -> b.
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldMap f = foldr (mappend . f) mempty

Traverse делает то же самое обобщение от списков к проходимым типам, но для mapM: 

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

(Когда mapM был впервые определен, класса Applicative не было; если бы он был, вместо него можно было бы определить mapA :: Applicative f => (a -> f b) -> [a] -> f [b]; ограничение Monad было бы сильнее, чем было необходимо.)

Applicative является моноидальным по своей природе, поэтому в Traverse не было необходимости для типа различия, который рисует foldr / foldMap.

0 голосов
/ 06 апреля 2019

В статье (и соответствующем отрывке из Викиучебника ) говорится о том, как эффекты (или, если использовать там язык, контексты) аппликативных значений можно комбинировать моноидально. Связь с Foldable заключается в том, что сворачивание в виде списков в конечном итоге сводится к моноидальному объединению значений (см. ответ Чепнера , а также Foldr / Foldl бесплатно, когда Tree реализует Foldable foldmap? . Что касается аппликативной части контекста, есть несколько способов посмотреть на это. Один из них отмечает, что для любых Applicative f и Monoid m, f m является моноидом, с pure mempty как mempty и liftA2 mappend как mappend ( этот Ap тип из редуктора пакет свидетельствует об этом). Для конкретного примера давайте выберем f ~ Maybe и m ~ (). Это оставляет нам четыре возможных комбинации: 

liftA2 mappend (Just ()) (Just ()) = Just ()
liftA2 mappend (Just ()) Nothing   = Nothing
liftA2 mappend Nothing   (Just ()) = Nothing
liftA2 mappend Nothing   Nothing   = Nothing

Теперь контрастируйте с All, моноидом Bool с (&&) как mappend: 

mappend (All True)  (All True)  = All True
mappend (All True)  (All False) = All False
mappend (All False) (All True)  = All False
mappend (All False) (All False) = All False

Они идеально соответствуют: Just () означает True, Nothing для False и liftA2 mappend для (&&).

Теперь давайте еще раз посмотрим на пример Wikibook: 

deleteIfNegative :: (Num a, Ord a) => a -> Maybe a
deleteIfNegative x = if x < 0 then Nothing else Just x

rejectWithNegatives :: (Num a, Ord a, Traversable t) => t a -> Maybe (t a)
rejectWithNegatives = traverse deleteIfNegative

GHCi> rejectWithNegatives [2,4,8]
Just [2,4,8]
GHCi> rejectWithNegatives [2,-4,8]
Nothing

Значения Maybe, сгенерированные путем применения deleteIfNegative к значениям в списках, моноидально объединяются, как показано выше, так что мы получаем Nothing, если только all значения Maybe Just.

К этому вопросу также можно подойти в противоположном направлении. Через экземпляр Applicative для Const ... 

-- I have suppressed a few implementation details from the instance used by GHC.
instance Monoid m => Applicative (Const m) where
    pure _ = Const mempty
    Const x <*> Const y = Const (x `mappend` y)

... мы можем получить Applicative из любого Monoid, так что (<*>) объединяет моноидальные значения моноидально. Это позволяет определять foldMap и друзей в терминах traverse.

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

...