Что может сделать Арроуз, что Монады не могут?

Стрелки, похоже, набирают популярность в сообществе Haskell, но мне кажется, что Monads являются более мощными. Что получается с помощью стрелок? Почему вместо Monads нельзя использовать?

Ответ 1

Мне всегда было трудно думать о проблеме в этих терминах: что получается при использовании стрелок. Как отмечали другие комментаторы, каждая монада может тривиально превращаться в стрелу. Итак, монада может делать все стрелки. Однако мы можем сделать стрелки, которые не являются монадами. То есть мы можем создавать типы, которые могут выполнять эти действия со стрелками, не заставляя их поддерживать монадическое связывание. Это может показаться не таким, но монадическая функция связывания на самом деле является довольно ограничительной (следовательно, мощной) операцией, которая дисквалифицирует многие типы.

Смотрите, чтобы поддерживать привязку, вы должны уметь утверждать, что независимо от типа ввода, то, что выйдет, будет завернуто в монаду.

(>>=) :: forall a b. m a -> (a -> m b) -> m b

Но как бы мы определили bind для типа типа data Foo a = F Bool a Конечно, мы могли бы объединить один Foo a с другим, но как бы мы объединили Bools. Представьте, что Bool отметил, скажем, изменилось ли значение другого параметра. Если у меня есть a = Foo False whatever и я привязываю его к функции, я понятия не имею, изменится ли эта функция whatever. Я не могу написать привязку, которая правильно устанавливает Bool. Это часто называют проблемой статической метаинформации. Я не могу проверить связанную функцию, чтобы определить, изменит ли она whatever.

Есть несколько других подобных случаев: типы, которые представляют собой мутирующие функции, парсеры, которые могут выйти рано и т.д. Но основная идея такова: монады устанавливают высокий бар, который не все типы могут очистить. Стрелки позволяют вам создавать типы (которые могут или не могут поддерживать этот высокий стандарт привязки) мощными способами без необходимости связывания. Конечно, вы теряете часть монад.

Мораль истории: ничто из стрелки не может сделать эту монаду, потому что монада всегда может быть превращена в стрелу. Однако иногда вы не можете создавать свои типы в монады, но вы все же хотите, чтобы они имели большую часть композиционной гибкости и мощности монад.

Многие из этих идей были вдохновлены превосходным Понимание Haskell Arrows

Ответ 2

Каждая монада порождает стрелку

newtype Kleisli m a b = Kleisli (a -> m b)
instance Monad m => Category (Kleisli m) where
   id = Kleisli return
   (Kleisli f) . (Kleisli g) = Kleisli (\x -> (g x) >>= f)
instance Monad m => Arrow (Kleisli m) where
   arr f = Kleisli (return . f)
   first (Kleisli f) = Kleisli (\(a,b) -> (f a) >>= \fa -> return (fa,b))

Но есть стрелки, которые не являются монадами. Таким образом, есть стрелки, которые делают то, что вы не можете сделать с монадами. Хорошим примером является трансформатор стрелки для добавления некоторой статической информации.

data StaticT m c a b = StaticT m (c a b)
instance (Category c, Monoid m) => Category (StaticT m c) where
   id = StaticT mempty id
   (StaticT m1 f) . (StaticT m2 g) = StaticT (m1 <> m2) (f . g)
instance (Arrow c, Monoid m) => Arrow (StaticT m c) where
   arr f = StaticT mempty (arr f)
   first (StaticT m f) = StaticT m (first f)

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

Ответ 3

Ну, я собираюсь немного обмануть здесь, изменив вопрос от Arrow до Applicative. Применяются те же самые мотивы, и я знаю аппликаторы лучше, чем стрелки. (И фактически каждый Arrow также является Applicative, но не наоборот, поэтому я просто немного уменьшаю его вниз по склону до Functor.)

Так же, как каждый Monad является Arrow, каждый Monad также является Applicative. Есть Applicatives, которые не являются Monad (например, ZipList), поэтому один возможный ответ.

Но предположим, что мы имеем дело с типом, который допускает экземпляр Monad, а также Applicative. Почему мы можем использовать экземпляр Applicative вместо Monad? Поскольку Applicative менее эффективен, и это приносит пользу:

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

В качестве примера первого, я работал над проектированием своего рода OLAP с использованием Applicative s. Тип допускает экземпляр Monad, но я сознательно избегал этого, потому что я хочу, чтобы запросы были менее мощными, чем позволял Monad. Applicative означает, что каждый расчет будет снижаться до прогнозируемого количества запросов.

В качестве примера последнего я буду использовать игрушечный пример из моей все еще развивающейся операционной библиотеки Applicative. Если вместо этого вы записываете монаду Reader как операционную программу Applicative, вы можете проверить полученный Reader, чтобы подсчитать, сколько раз они используют операцию ask:

{-# LANGUAGE GADTs, RankNTypes, ScopedTypeVariables #-}

import Control.Applicative.Operational

-- | A 'Reader' is an 'Applicative' program that uses the 'ReaderI' 
-- instruction set.
type Reader r a = ProgramAp (ReaderI r) a

-- | The only 'Reader' instruction is 'Ask', which requires both the
-- environment and result type to be @[email protected]
data ReaderI r a where
    Ask :: ReaderI r r

ask :: Reader r r
ask = singleton Ask

-- | We run a 'Reader' by translating each instruction in the instruction set
-- into an @r -> [email protected] function.  In the case of 'Ask' the translation is 'id'.
runReader :: forall r a. Reader r a -> r -> a
runReader = interpretAp evalI
    where evalI :: forall x. ReaderI r x -> r -> x
          evalI Ask = id

-- | Count how many times a 'Reader' uses the 'Ask' instruction.  The 'viewAp'
-- function translates a 'ProgramAp' into a syntax tree that we can inspect.
countAsk :: forall r a. Reader r a -> Int
countAsk = count . viewAp
    where count :: forall x. ProgramViewAp (ReaderI r) x -> Int
          -- Pure :: a -> ProgamViewAp instruction a
          count (Pure _) = 0
          -- (:<**>) :: instruction a 
          --         -> ProgramViewAp instruction (a -> b)
          --         -> ProgramViewAp instruction b
          count (Ask :<**> k) = succ (count k)

Насколько я понимаю, вы не можете написать countAsk, если вы реализуете Reader как монаду. (Мое понимание приходит от запроса прямо здесь, в переполнении стека, я добавлю.)

Этот же мотив - фактически одна из идей, стоящих за Arrow s. Одним из важных мотивирующих примеров для Arrow был дизайн комбинатора парсера, который использует "статическую информацию" для повышения производительности, чем монадические парсеры. То, что они подразумевают под "статической информацией", более или менее такое же, как в моем примере Reader: возможно написать экземпляр Arrow, где анализаторы могут быть проверены очень как мой Reader. Затем библиотека синтаксического анализа может, перед выполнением анализатора, проверить его, чтобы увидеть, может ли он заранее предсказать, что он потерпит неудачу, и пропустите его в этом случае.

В одном из прямых комментариев к вашему вопросу, jberryman упоминает, что стрелы могут фактически потерять популярность. Я бы добавил, что, как я вижу, Applicative - это то, что стрелки теряют популярность.

Литература:

Паоло Каприотти и Амбрус Капоши, Бесплатные аппликативные функторы. Очень рекомендуется.
Герго Эрди, "Статический анализ с применением" . Вдохновенный, но мне трудно следовать...

Ответ 4

Вопрос не совсем правильный. Он спрашивает, почему вы едите апельсины вместо яблок, так как яблоки кажутся более питательными вокруг.

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

Haskell Wiki перечисляет несколько введений для стрелок. В частности, Wikibook - это хорошее введение на высоком уровне, а учебник Джона Хьюза - хороший обзор различных видов стрелок.

Для примера в реальном мире сравните этот учебник, в котором используется интерфейс на основе стрелок Hakyll 3, с примерно то же самое в интерфейсе Hakyll 4 на основе монады.