Что такое стрелки и как их использовать?

Question

Я пытался понять значение стрелок , но я не понял их.

Я использовал учебник Wikibooks. Я думаю, что проблема Wikibook в основном в том, что она написана для того, кто уже понимает эту тему.

Может кто-нибудь объяснить, что такое стрелки и как я могу их использовать?

Answer 1

Я не знаю учебник, но я думаю, что стрелки легче всего понять, если вы посмотрите на некоторые конкретные примеры.Самая большая проблема, с которой я столкнулся, изучая, как использовать стрелки, заключалась в том, что ни один из учебных пособий или примеров на самом деле не показал, как использовать стрелки, а только как их составить.Итак, учитывая это, вот мой мини-учебник.Я рассмотрю две разные стрелки: функции и пользовательский тип стрелки MyArr.

-- type representing a computation
data MyArr b c = MyArr (b -> (c,MyArr b c))

1) Стрелка - это вычисление от ввода указанного типа до вывода указанного типа.Класс типов стрелки принимает три аргумента типа: тип стрелки, тип ввода и тип вывода.Рассматривая заголовок экземпляра для экземпляров стрелок, мы находим:

instance Arrow (->) b c where
instance Arrow MyArr b c where

Стрелка (либо (->), либо MyArr) является абстракцией вычисления.

Для функции b -> c, b - это вход, а c - это выход.
Для MyArr b c, b - это вход, а c - это выход.

2) Для фактического запускавычисление стрелки, вы используете функцию, специфичную для вашего типа стрелки.Для функций вы просто применяете функцию к аргументу.Для других стрелок должна быть отдельная функция (например, runIdentity, runState и т. Д. Для монад).

-- run a function arrow
runF :: (b -> c) -> b -> c
runF = id

-- run a MyArr arrow, discarding the remaining computation
runMyArr :: MyArr b c -> b -> c
runMyArr (MyArr step) = fst . step

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

-- run a function arrow over multiple inputs
runFList :: (b -> c) -> [b] -> [c]
runFList f = map f

-- run a MyArr over multiple inputs.
-- Each step of the computation gives the next step to use
runMyArrList :: MyArr b c -> [b] -> [c]
runMyArrList _ [] = []
runMyArrList (MyArr step) (b:bs) = let (this, step') = step b
                                   in this : runMyArrList step' bs

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

Вот MyArr, который ведет подсчет количества полученных входов:

-- count the number of inputs received:
count :: MyArr b Int
count = count' 0
  where
    count' n = MyArr (\_ -> (n+1, count' (n+1)))

Теперь функция runMyArrList countпримет длину списка n в качестве входных данных и вернет список значений Ints от 1 до n.

Обратите внимание, что мы до сих пор не использовали никаких функций "стрелок", то есть методов класса Arrow или функций, написанных в терминахиз них.

4) Большая часть кода выше специфична для каждого экземпляра Arrow [1].Все в Control.Arrow (и Control.Category) - это составление стрелок для создания новых стрелок.Если мы представим, что Category является частью Arrow, а не отдельным классом:

-- combine two arrows in sequence
>>> :: Arrow a => a b c -> a c d -> a b d

-- the function arrow instance
-- >>> :: (b -> c) -> (c -> d) -> (b -> d)
-- this is just flip (.)

-- MyArr instance
-- >>> :: MyArr b c -> MyArr c d -> MyArr b d

Функция >>> берет две стрелки и использует вывод первой в качестве ввода для второй.

Вот еще один оператор, обычно называемый "fanout":

-- &&& applies two arrows to a single input in parallel
&&& :: Arrow a => a b c -> a b c' -> a b (c,c')

-- function instance type
-- &&& :: (b -> c) -> (b -> c') -> (b -> (c,c'))

-- MyArr instance type
-- &&& :: MyArr b c -> MyArr b c' -> MyArr b (c,c')

-- first and second omitted for brevity, see the accepted answer from KennyTM's link
-- for further details.

Поскольку Control.Arrow предоставляет средства для объединения вычислений, вот один пример:

-- function that, given an input n, returns "n+1" and "n*2"
calc1 :: Int -> (Int,Int)
calc1 = (+1) &&& (*2)

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

Класс типа Monad предоставляет нам средство для объединения монадических вычислений в одно новое монадическое вычисление с использованием >>=функция.Точно так же класс Arrow предоставляет нам средства для объединения вычислений со стрелками в одно новое вычисление со стрелками с использованием нескольких примитивных функций (first, arr и ***, с >>> и id из Control.Category).Также похож на монады, вопрос "Что делает стрела?"не может быть общего ответа.Это зависит от стрелки.

К сожалению, я не знаю многих примеров экземпляров стрелок в дикой природе.Функции и FRP кажутся наиболее распространенными приложениями.HXT - единственное другое важное использование, которое приходит на ум.

[1] За исключением count.Можно написать функцию подсчета, которая делает то же самое для любого экземпляра ArrowLoop.

Answer 2

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

Одной операцией для Functor является fmap, которая служит обобщенной версией map в списках.Это почти вся цель класса типов;он определяет «вещи, которые вы можете отобразить».Таким образом, в некотором смысле Functor представляет обобщение этого конкретного аспекта списков.

Операции для Monoid являются обобщенными версиями пустого списка и (++), и он определяет «вещи, которые могут бытьобъединено ассоциативно, с определенной вещью, которая является ценностью идентичности ".Списки - в значительной степени простейшая вещь, которая подходит под это описание, и Monoid представляет обобщение этого аспекта списков.

Так же, как и в двух предыдущих случаях, операции над классом типа Category выполняютсяобобщенные версии id и (.), и он определяет «вещи, соединяющие два типа в определенном направлении, которые можно соединить лицом к лицу».Таким образом, это представляет собой обобщение этого аспекта функций .Примечательно, что в обобщение не включены карри или приложения функций.

Класс Arrow строится из Category, но основная концепция та же: Arrow s - это вещи, которые сочетаются как функции ииметь «стрелку идентичности», определенную для любого типа.Дополнительные операции, определенные в самом классе Arrow, просто определяют способ поднять произвольную функцию до Arrow и способ объединения двух стрелок «параллельно» в виде одной стрелки между кортежами.

Итакпервое, что здесь следует иметь в виду, это то, что выражения, создающие Arrow s, по сути, являются сложной композицией функций .Комбинаторы, такие как (***) и (>>>), предназначены для написания стиля "pointfree", в то время как запись proc дает возможность назначать временные имена для входов и выходов при подключении.

Полезно отметитьздесь то, что, хотя Arrow s иногда описывают как "следующий шаг" из Monad s, там действительно нет очень значимых отношений.Для любого Monad вы можете работать со стрелками Клейсли, которые являются просто функциями с типом, подобным a -> m b.Оператор (<=<) в Control.Monad является составом стрелки для них.С другой стороны, Arrow s не даст вам Monad, если вы не включите класс ArrowApply.Так что прямой связи как таковой нет.

Ключевое отличие здесь заключается в том, что, хотя Monad s можно использовать для последовательности вычислений и выполнения действий шаг за шагом, Arrow s в некотором смысле "вне времени"«как обычные функции.Они могут включать в себя дополнительное оборудование и функциональность, которые объединяются с помощью (.), но это больше похоже на построение конвейера, а не на накопление действий.

Другие классы связанных типов добавляют дополнительные функции к стрелке, такие как возможностьобъединить стрелки с Either и (,).

---

Мой любимый пример Arrow - потоковые преобразователи с состоянием , которые выглядят примерно так:

data StreamTrans a b = StreamTrans (a -> (b, StreamTrans a b))

Стрелка StreamTrans преобразует входное значение в выходную и "обновленную" версию самого себя;рассмотрим, чем это отличается от состояния Monad.

Запись экземпляров для Arrow и связанных с ним классов типов для указанного выше типа может быть хорошим упражнением для понимания того, как они работают!

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

Answer 3

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

Чтобы увидеть, насколько это практически полезно, подумайте, что у вас есть куча функции, которые вы хотите составить, где некоторые из них являются чистыми, а некоторые монадическая. Например, f :: a -> b, g :: b -> m1 c и h :: c -> m2 d.

Зная каждый из задействованных типов, я мог бы создать композицию вручную, но тип выхода композиции должен отражать промежуточный типы монад (в приведенном выше случае m1 (m2 d)). Что если я просто хочу лечить функции, как если бы они были просто a -> b, b -> c и c -> d? То есть, Я хочу абстрагироваться от наличия монад и рассуждений только о базовые типы. Я могу использовать стрелки, чтобы сделать именно это.

Вот стрелка, которая абстрагирует присутствие IO для функций в IO монада, такая, что я могу составить их с чистыми функциями без составление кода, который должен знать, что IO задействован . Начнем с определения IOArrow для переноса функций IO:

data IOArrow a b = IOArrow { runIOArrow :: a -> IO b }

instance Category IOArrow where
  id = IOArrow return
  IOArrow f . IOArrow g = IOArrow $ f <=< g

instance Arrow IOArrow where
  arr f = IOArrow $ return . f
  first (IOArrow f) = IOArrow $ \(a, c) -> do
    x <- f a
    return (x, c)

Затем я делаю несколько простых функций, которые хочу написать:

foo :: Int -> String
foo = show

bar :: String -> IO Int
bar = return . read

И используйте их:

main :: IO ()
main = do
  let f = arr (++ "!") . arr foo . IOArrow bar . arr id
  result <- runIOArrow f "123"
  putStrLn result

Здесь я звоню IOArrow и запускаюIOArrow, но если бы я передавал эти стрелки вокруг в библиотеке полиморфных функций, они должны были бы только принять аргументы типа "Стрелка a => a b c". Ни один из библиотечного кода не понадобится быть осведомленным, что монада была вовлечена. Только создатель и конечный пользователь стрелка должна знать.

Обобщение IOArrow для работы для функций в любой монаде называется "Kleisli" стрелка ", и уже есть встроенная стрелка для этого:

main :: IO ()
main = do
  let g = arr (++ "!") . arr foo . Kleisli bar . arr id
  result <- runKleisli g "123"
  putStrLn result

Конечно, вы также можете использовать операторы композиции стрелок и синтаксис proc, чтобы немного проясните, какие стрелки задействованы:

arrowUser :: Arrow a => a String String -> a String String
arrowUser f = proc x -> do
  y <- f -< x
  returnA -< y

main :: IO ()
main = do
  let h =     arr (++ "!")
          <<< arr foo
          <<< Kleisli bar
          <<< arr id
  result <- runKleisli (arrowUser h) "123"
  putStrLn result

Здесь должно быть ясно, что хотя main знает, что монада IO задействована, arrowUser нет. Не было бы никакого способа «спрятать» IO от arrowUser без стрелок - не прибегая к unsafePerformIO, чтобы повернуть промежуточное монадическое значение обратно в чистое (и, таким образом, теряет этот контекст навсегда). Например:

arrowUser' :: (String -> String) -> String -> String
arrowUser' f x = f x

main' :: IO ()
main' = do
  let h      = (++ "!") . foo . unsafePerformIO . bar . id
      result = arrowUser' h "123"
  putStrLn result

Попробуйте написать это без unsafePerformIO и без arrowUser' без необходимости иметь дело с любыми аргументами типа Monad.

Answer 4

Есть лекционные заметки Джона Хьюза из мастерской AFP (Расширенное функциональное программирование). Обратите внимание, что они были написаны до того, как классы Arrow были изменены в базовых библиотеках:

http://www.cse.chalmers.se/~rjmh/afp-arrows.pdf

Answer 5

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

function(x) {
  func1result = func1(x)
  if(func1result == null) {
    return null
  } else {
    func2result = func2(func1result)
    if(func2result == null) {
      return null
    } else {
      func3(func2result)
    } 

Таким образом, по существу, для некоторого значения x сначала вызовите одну функцию, которая, как мы предполагаем, может вернуть null (func1), другую, которая может повторно выполнить null или присвоить null взаимозаменяемо, наконец, третью функция, которая также может возвращать null. Теперь, учитывая значение x, передайте x в func3, только тогда, если оно не возвращает null, передайте это значение в func2, и только если это значение не равно нулю, передайте это значение в func1. Он более детерминирован, а поток управления позволяет создавать более сложные обработки исключений.

Здесь мы можем использовать композицию стрелки: (func3 <=< func2 <=< func1) x.