-
Arrows -
- С момента:
-
6.8.1
Включить стрелочную нотацию.
Стрелки являются обобщением монад, введенных Джоном Хьюзом. Для получения более подробной информации см.
- «Обобщение монад до стрелок», Джон Хьюз, в Science of Computer Programming 37, стр. 67–111, май 2000 г. Статья, в которой были введены стрелки: дружественное введение, мотивированное примерами программирования.
- «Новая нотация для стрелок», Росс Патерсон, в ICFP, сентябрь 2001 г. Введена здесь описанная нотация.
- «Стрелки и вычисления», Росс Патерсон, в The Fun of Programming, Palgrave, 2003 г.
- «Программирование со стрелками», Джон Хьюз, на 5-й Международной летней школе по продвинутому функциональному программированию, Lecture Notes in Computer Science том 3622, Springer, 2004 г. Эта статья включает другое введение в нотацию с практическими примерами.
- «Правила типов и трансляции для стрелочной нотации в GHC», Росс Патерсон и Саймон Пейтон Джонс, 16 сентября 2004 г. Краткое изложение формальных правил, используемых (извлеченных из комментариев в исходном коде).
- Веб-страница стрелок по адресу
https://www.haskell.org/arrows/<https://www.haskell.org/arrows/>`__.
С расширением Arrows, GHC поддерживает описанную во второй из этих статей стрелочную нотацию, переводя ее с помощью комбинаторов из модуля Control.Arrow. Далее следует краткое введение в нотацию; она не будет иметь особого смысла, если вы не читали статью Хьюза.
Расширение добавляет новый тип выражения для определения стрелок:
exp10 ::= ...
| proc apat -> cmd
где proc — новое ключевое слово. Переменные шаблона привязаны в теле proc-выражения, представляющего собой новый тип, называемый командой. Синтаксис команд следующий:
cmd ::= exp10 -< exp
| exp10 -<< exp
| cmd0
где ⟨cmd⟩0 до ⟨cmd⟩9 определены с использованием инфиксных операторов, как и для выражений, и
cmd10 ::= \ apat ... apat -> cmd
| let decls in cmd
| if exp then cmd else cmd
| case exp of { calts }
| do { cstmt ; ... cstmt ; cmd }
| fcmd
fcmd ::= fcmd aexp
| ( cmd )
| (| aexp cmd ... cmd |)
cstmt ::= let decls
| pat <- cmd
| rec { cstmt ; ... cstmt [;] }
| cmd
где ⟨calts⟩ похожи на ⟨alts⟩, за исключением того, что тела являются командами, а не выражениями.
Команды производят значения, но (как вычислительные монады) могут возвращать более одного значения, или ни одного, и могут выполнять и другие действия. В основном, знание монадической нотации является хорошим руководством для использования команд. Однако значения выражений, даже монадических, определяются значениями переменных, которые они содержат; это не обязательно так для команд.
Простым примером новой нотации является выражение
proc x -> f -< x+1
Мы называем это процедурой или абстракцией стрелки. Как и в случае с лямбда-выражением, переменная x — новая переменная, связанная в рамках proc-выражения. Она относится к вводу в стрелку. В приведенном выше примере -< — это не идентификатор, а новая зарезервированная метка, используемая для построения команд из выражения стрелочного типа и выражения, которое нужно подать в качестве входных данных этой стрелке. (Странный вид станет понятнее позже.) Его можно прочитать как аналог применения для стрелок. Приведенный выше пример эквивалентен выражению Haskell
arr (\ x -> x+1) >>> f
Это не имело бы смысла, если выражение слева от -< включает связанную переменную x. Более общим образом, выражение слева от -< может не включать какие-либо локальные переменные, т. е. переменные, связанные в текущей абстракции стрелки. Для такой ситуации существует вариант -<<, как в
proc x -> f x -<< x+1
что эквивалентно
arr (\ x -> (f x, x+1)) >>> app
следовательно, в этом случае стрелка должна принадлежать к классу ArrowApply. Такая стрелка эквивалентна монаде, поэтому, если вы используете эту форму, вам может быть удобнее использовать монадическую формулировку.
6.2.19.1. do-нотация для команд
Другая форма команды — это форма do-нотации. Например, вы можете написать
proc x -> do
y <- f -< x+1
g -< 2*y
let z = x+y
t <- h -< x*z
returnA -< t+z
Вы можете прочитать это так же, как обычную do-нотацию, но с командами вместо монадических выражений. В первой строке значение x+1 передается в качестве входных данных стрелке f, и ее вывод сопоставляется с y. В следующей строке вывод отбрасывается. Стрелка returnA определяется в модуле Control.Arrow как arr id. Приведенный выше пример рассматривается как сокращение для
arr (\ x -> (x, x)) >>>
first (arr (\ x -> x+1) >>> f) >>>
arr (\ (y, x) -> (y, (x, y))) >>>
first (arr (\ y -> 2*y) >>> g) >>>
arr snd >>>
arr (\ (x, y) -> let z = x+y in ((x, z), z)) >>>
first (arr (\ (x, z) -> x*z) >>> h) >>>
arr (\ (t, z) -> t+z) >>>
returnA
Обратите внимание, что переменные, которые не используются позже в композиции, исключаются. После упрощения с использованием правил переписывания (см. Правила переписывания) , определенных в модуле Control.Arrow, это сводится к
arr (\ x -> (x+1, x)) >>>
first f >>>
arr (\ (y, x) -> (2*y, (x, y))) >>>
first g >>>
arr (\ (_, (x, y)) -> let z = x+y in (x*z, z)) >>>
first h >>>
arr (\ (t, z) -> t+z)
что вы могли бы написать вручную. Со стрелочной нотацией GHC отслеживает все эти наборы переменных за вас.
Обратите внимание, что хотя приведенный выше перевод предполагает, что let-связанные переменные, такие как z , должны быть мономорфными, фактический перевод генерирует Core, поэтому полиморфные переменные разрешены.
Также возможно иметь взаимно рекурсивные привязки, используя новое ключевое слово rec, как в следующем примере:
counter :: ArrowCircuit a => a Bool Int
counter = proc reset -> do
rec output <- returnA -< if reset then 0 else next
next <- delay 0 -< output+1
returnA -< output
Перевод таких форм использует комбинатор loop, поэтому рассматриваемая стрелка должна принадлежать к классу ArrowLoop.
6.2.19.2. Условные команды
В предыдущем примере мы использовали условное выражение для построения входных данных для стрелки. Иногда мы хотим условно выполнить разные команды, как в
proc (x,y) ->
if f x y
then g -< x+1
else h -< y+2
что переводится как
arr (\ (x,y) -> if f x y then Left x else Right y) >>>
(arr (\x -> x+1) >>> g) ||| (arr (\y -> y+2) >>> h)
Поскольку перевод использует |||, рассматриваемая стрелка должна принадлежать к классу ArrowChoice.
Также есть case команды, такие как
case input of
[] -> f -< ()
[x] -> g -< x+1
x1:x2:xs -> do
y <- h -< (x1, x2)
ys <- k -< xs
returnA -< y:ys
Синтаксис такой же, как и для case выражений, за исключением того, что тела альтернатив являются командами, а не выражениями. Трансляция аналогична трансляции if команд.
6.2.19.3. Определение собственных управляющих структур
Как мы видели, стрелочная нотация предоставляет конструкции, моделированные на конструкциях для выражений, для последовательности, рекурсии значений и условных выражений. Но подходящие комбинаторы, которые вы можете определить в обычном Haskell, также могут использоваться для построения новых команд из существующих. Основная идея в том, что команда определяет стрелку от сред до значений. Эти среды присваивают значения свободным локальным переменным команды. Таким образом, комбинаторы, которые создают стрелки из стрелок, также могут использоваться для построения команд из команд. Например, класс ArrowPlus включает комбинатор
ArrowPlus a => (<+>) :: a b c -> a b c -> a b c
поэтому мы можем использовать его для построения команд:
expr' = proc x -> do
returnA -< x
<+> do
symbol Plus -< ()
y <- term -< ()
expr' -< x + y
<+> do
symbol Minus -< ()
y <- term -< ()
expr' -< x - y
(do в первой строке необходимо, чтобы первое <+> ... не интерпретировалось как часть выражения в предыдущей строке.) Это эквивалентно
expr' = (proc x -> returnA -< x)
<+> (proc x -> do
symbol Plus -< ()
y <- term -< ()
expr' -< x + y)
<+> (proc x -> do
symbol Minus -< ()
y <- term -< ()
expr' -< x - y)
Мы на самом деле используем <+> здесь с более конкретным типом
ArrowPlus a => (<+>) :: a (e,()) c -> a (e,()) c -> a (e,()) c
Это важно, чтобы этот оператор был полиморфным по e (представляющему среду входных данных команды, а затем ее подкоманд) и удовлетворял соответствующему свойству естественности
arr (first k) >>> (f <+> g) = (arr (first k) >>> f) <+> (arr (first k) >>> g)
по крайней мере, для строгих k. (Это должно быть автоматическим, если вы не используете seq.) Это гарантирует, что среды, видимые подкомандами, являются средами всей команды, а также позволяет переводу безопасно обрезать эти среды. (Второй компонент пар входных данных может содержать значения ввода без имени, как описано в следующей секции.) Оператор также не должен использовать какие-либо переменные, определенные в рамках текущей абстракции стрелки.
Мы могли бы определить свой оператор
untilA :: ArrowChoice a => a (e,s) () -> a (e,s) Bool -> a (e,s) ()
untilA body cond = proc x -> do
b <- cond -< x
if b then returnA -< ()
else do
body -< x
untilA body cond -< x
и использовать его таким же образом. Конечно, этот инфиксный синтаксис имеет смысл только для бинарных операторов; также есть более общий синтаксис, использующий специальные скобки:
proc x -> do
y <- f -< x+1
(|untilA (increment -< x+y) (within 0.5 -< x)|)
