6.2.20. Стрелочная нотация

6.2.20.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.20.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.20.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)|)

6.2.20.4. Примитивные конструкции

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

handleA :: ... => a (e,s) c -> a (e,(Ex,s)) c -> a (e,s) c

где Ex — тип обрабатываемых исключений. Затем его можно использовать со стрелочной нотацией, написав команду

body `handleA` \ ex -> handler

так что, если в команде body возникает исключение, переменной ex присваивается значение исключения и запускается команда handler, которая обычно обращается к ex. Хотя синтаксис здесь похож на функциональную лямбда-абстракцию, речь идёт о командах, и здесь действует иной механизм. Вход стрелки, представленной командой, состоит из значений свободных локальных переменных команды и стека анонимных значений. Во всех предыдущих примерах мы не делали предположений об этом стеке. Во втором аргументе handleA значение исключения добавлено во входной стек обработчика. Форма команды с лямбда-абстракцией лишь присваивает этому значению имя.

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

a (e, (t1, ... (tn, ())...)) t

где ⟨e⟩ — полиморфная переменная (представляющая окружение), а ⟨ti⟩ — типы значений в стеке, причём ⟨t1⟩ находится «на вершине». Полиморфная переменная ⟨e⟩ не должна встречаться в ⟨a⟩, ⟨ti⟩ или ⟨t⟩. Однако используемые стрелки не обязаны быть одинаковыми. Вот ещё несколько примеров подходящих операторов:

bracketA :: ... => a (e,s) b -> a (e,(b,s)) c -> a (e,(c,s)) d -> a (e,s) d
runReader :: ... => a (e,s) c -> a' (e,(State,s)) c
runState :: ... => a (e,s) c -> a' (e,(State,s)) (c,State)

Дополнительный вход, необходимый командам, построенным с помощью двух последних операторов, можно передать, применив их к обычным выражениям, например:

proc x -> do
        s <- ...
        (|runReader (do { ... })|) s

это добавляет s в стек входных данных команды, построенной с помощью runReader.

Формы команд для лямбда-абстракции и применения аналогичны формам для выражений. В частности, правила бета и эта описывают эквивалентности команд. Эти три возможности (операторы, лямбда-абстракция и применение) составляют основу нотации; всё остальное можно построить с их помощью, хотя результат будет несколько громоздким. Например, можно имитировать do-нотацию, определив

bind :: Arrow a => a (e,s) b -> a (e,(b,s)) c -> a (e,s) c
u `bind` f = returnA &&& u >>> f

bind_ :: Arrow a => a (e,s) b -> a (e,s) c -> a (e,s) c
u `bind_` f = u `bind` (arr fst >>> f)

Также можно имитировать if, определив

cond :: ArrowChoice a => a (e,s) b -> a (e,s) b -> a (e,(Bool,s)) b
cond f g = arr (\ (e,(b,s)) -> if b then Left (e,s) else Right (e,s)) >>> f ||| g

6.2.20.5. Отличия от статьи

• Вместо единой формы применения стрелки (стрелочного хвоста) с двумя вариантами трансляции в реализации предусмотрены две формы: -< (первого порядка) и -<< (высшего порядка).
• Пользовательские операторы обозначаются банановыми скобками, а не новым ключевым словом form.
• В статье и предыдущей реализации значения стека объединялись справа от окружения в одном аргументе, а теперь окружение и стек передаются как отдельные аргументы.

6.2.20.6. Переносимость

Хотя стрелочную нотацию напрямую реализует только GHC, существует также препроцессор (доступный на веб-странице о стрелках), который транслирует стрелочную нотацию в Haskell 98 для использования с другими системами Haskell. Программы со стрелками всё равно стоит проверять с помощью GHC: отладить ошибки типов в выходных данных препроцессора непросто. Модули, предназначенные и для GHC, и для препроцессора, должны соблюдать некоторые дополнительные ограничения:

• Модуль должен импортировать Control.Arrow.
• Препроцессор не поддерживает другие расширения Haskell. Их необходимо вынести в отдельные модули.
• Поскольку препроцессор генерирует Haskell (а не Core), связанные с let переменные являются мономорфными.