Почему взаимная уступка делает ArrowApply и Monads эквивалентными, в отличие от Arrow и Applicative? - PullRequest
Новая
       89

Почему взаимная уступка делает ArrowApply и Monads эквивалентными, в отличие от Arrow и Applicative?

8 голосов
/ 23 января 2020

Вот ТАК, что я собираюсь сослаться на . Кроме того, я собираюсь использовать те же фрагменты, что и ОП в этом вопросе, чтобы не разделять материалы .

Это широко известно , что * Экземпляр 1009 * дает монаду и наоборот: 

newtype ArrowMonad a b = ArrowMonad (a () b)

instance Arrow a => Functor (ArrowMonad a) where
    fmap f (ArrowMonad m) = ArrowMonad $ m >>> arr f

instance Arrow a => Applicative (ArrowMonad a) where
   pure x = ArrowMonad (arr (const x))
   ArrowMonad f <*> ArrowMonad x = ArrowMonad (f &&& x >>> arr (uncurry id))

instance ArrowApply a => Monad (ArrowMonad a) where
    ArrowMonad m >>= f = ArrowMonad $
        m >>> arr (\x -> let ArrowMonad h = f x in (h, ())) >>> app

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Monad m => Category (Kleisli m) where
    id = Kleisli return
    (Kleisli f) . (Kleisli g) = Kleisli (\b -> g b >>= f)

instance Monad m => Arrow (Kleisli m) where
    arr f = Kleisli (return . f)
    first (Kleisli f) = Kleisli (\ ~(b,d) -> f b >>= \c -> return (c,d))
    second (Kleisli f) = Kleisli (\ ~(d,b) -> f b >>= \c -> return (d,c))

И пока я не наткнулся на запись , на которую ссылаются выше, я чувствовал, что этот фрагмент был правдоподобным доказательством эквивалентности ArrowApply и Monad классы. Тем не менее, знание того, что Arrow и Applicative, на самом деле, не эквивалентны , и следующий фрагмент заставил меня задуматься о полном доказательстве эквивалентности Monad и ArrowApply: 

newtype Arrplicative arr o a = Arrplicative{ runArrplicative :: arr o a }

instance (Arrow arr) => Functor (Arrplicative arr o) where
    fmap f = Arrplicative . (arr f .) . runArrplicative

instance (Arrow arr) => Applicative (Arrplicative arr o) where
    pure = Arrplicative . arr . const

    Arrplicative af <*> Arrplicative ax = Arrplicative $
        arr (uncurry ($)) . (af &&& ax)

newtype Applicarrow f a b = Applicarrow{ runApplicarrow :: f (a -> b) }

instance (Applicative f) => Category (Applicarrow f) where
    id = Applicarrow $ pure id
    Applicarrow g . Applicarrow f = Applicarrow $ (.) <$> g <*> f

instance (Applicative f) => Arrow (Applicarrow f) where
    arr = Applicarrow . pure
    first (Applicarrow f) = Applicarrow $ first <$> f

> Таким образом, если вы совершаете обратное путешествие по аппликативу, вы теряете некоторые особенности. Очевидно, что если приведены примеры, но я не могу сказать asp, как «круговое отключение» через Monad сохраняет все функции ArrowApply, так как изначально у нас была стрелка, которая зависит от некоторого ввода (a b c), но в конце мы получаем стрелу, вставленную в оболочку, у которой в качестве типа ввода (ArrowMonad (a () b)) указан тип блока (*1027*).

Очевидно, что я делаю здесь что-то ужасно неправильно, но не могу понять, что именно.

Что является полным доказательством того, что ArrowApply и Monad эквивалентны?

Что объясняют примеры неэквивалентности Arrow и Applicative? Обобщает ли одно другое?

Какова интерпретация всей этой ситуации в исчислении стрел и теории категорий?

Я был бы признателен за полные объяснения и советы, которые могли бы помочь составить правдоподобный фрагмент доказать себя.

1 Ответ

3 голосов
/ 24 января 2020

, так как изначально у нас была стрелка, которая зависит от некоторого ввода (a b c), но в конце мы получаем стрелу, принудительно вставленную в оболочку, у которой в качестве типа ввода указан тип блока (ArrowMonad (a () b))

Полагаю, это центральная точка беспорядка, и это действительно сбивает с толку. Мне нравится думать о стрелах как о морфизмах в декартовой моноидальной категории, где вы этого не получите, но класс Arrow на самом деле более ограничивающий, чем класс arr, что дает вам функтор от Hask в категорию. Но, что несколько удивительно, это также влечет за собой то, что вы получаете отображение в направлении other : любая стрелка может быть заменена функцией , которая дает просто стрелку тривиальной области. Конкретно, 

arrAsFunction :: Arrow k => k x y -> (x -> k () y)
arrAsFunction φ x = φ <<< arr (const x)

Ладно, это само по себе не будет слишком грубым - может быть, мы просто отбросили некоторую информацию здесь? - но с ArrowApply это на самом деле изоморфизм : вы можете вернуть исходную стрелку с помощью 

retrieveArrowFromFunction :: ∀ k x y .
          ArrowApply k => (x -> k () y) -> k x y
retrieveArrowFromFunction f = arr f' >>> app
 where f' :: x -> (k () y, ())
       f' x = (f x, ())

..., что именно то, что используется в Monad (ArrowMonad a) instance.

Таким образом, в результате получается: arr, требуя, чтобы вы могли встроить в категорию любую функцию Haskell, обеспечивает, что категория в основном сводится к функциям с некоторой оболочкой вокруг результата , что-то вроде стрелок Клейсли.

Проверьте некоторые другие иерархии теории категорий, чтобы увидеть, что это не фундаментальная особенность декартовых моноидальных категорий, но на самом деле артефакт Hask → k функтор. Например, в категориях с ограничениями Я отразил стандартные классы близко, с PreArrow в качестве класса декартовых моноидальных категорий, но намеренно держал arr вне его и не определял его c to Hask , потому что это слишком сильно снижает возможности категории и делает ее почти эквивалентной Hask -Kleisli.

...