Как создать стрелку, которая считает соединения?

(Это действительно то же самое, что и наблюдение Даниэля Вагнера, но я решил сделать его более дружелюбным.)

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

• Если тип или функция обещает, что подчиняется закону, который гласит x = y, клиенты этого класса не должны различать x и y.
• I.e., you should not be able to write a function f such that:
  • The law says that x = y;
  • Но f x /= f y

Теперь это не может быть абсолютным правилом. Возьмем, к примеру, сортировку; Сортировка слиянием и пузырьковая сортировка являются стабильными алгоритмами сортировки, и, следовательно, они «одинаковая функция» в том смысле, что вы не можете отличить их друг от друга, глядя на входные и выходные данные. Но если вы используете «побочный канал», такой как синхронизация, вы все равно можете отличить их друг от друга, но мы обычно исключаем это из рассмотрения, когда спрашиваем, подчиняется ли какой-либо код заданному закону.

Теперь, когда мы применим это к вашему типу K, проблема заключается в том, что вы можете написать программу, которая различает два выражения, которые согласно законам монад должны быть неразличимы. Например, в документации для Monad класс говорит, что:

Кроме того, операции Monad и Applicative должны соотноситься следующим образом:

pure = return
(<*>) = ap

И мы можем легко опровергнуть второй из них с помощью теста QuickCheck, подобного этому:

import Control.Monad (ap)
import Test.QuickCheck
import Test.QuickCheck.Function

-- Snipped your code for `K`

prop_ap :: Fun Int Int -> Int -> Bool
prop_ap f x = runK applicative 0 == runK monadic 0
    where applicative = pure (apply f) <*> pure x
          monadic = return (apply f) `ap` return x

Тестирование этого сразу не удается:

>>>  quickCheck prop_ap
*** Failed! Falsifiable (after 1 test and 2 shrinks): 
{_->0}
0

Причина здесь в том, что ваш экземпляр Monad выполняет +1, а ваш Applicative ничего подобного не делает. Таким образом, мы можем различать эквивалентные вычисления, но одно из них было построено с <*>, а другое с ap.

Как описано другими, вы не можете подсчитывать «соединения», такие как привязки или операции привязки стрелок, потому что тогда они не будут удовлетворять законам монады/стрелки.

Однако, что вы можете сделать, так это создать стрелку, в которой вы можете явно указать размеры своих строительных блоков, а затем вычислить размер такой схемы. Например: {-# ​​LANGUAGE Arrows #-}

import Control.Arrow
import qualified Control.Category as C

data A a b c = A { runA :: a b c, sizeA :: !Int }

Здесь мы определили преобразователь стрелки, который оборачивает существующую стрелку и добавляет ее размер.

instance (C.Category a) => C.Category (A a) where
    id = A C.id 0
    (A a1 s1) . (A a2 s2) = A (a1 C.. a2) (s1 + s2)

instance (Arrow a) => Arrow (A a) where
    arr f = A (arr f) 0
    first (A f s) = A (first f) s

instance (ArrowChoice a) => ArrowChoice (A a) where
    left (A f s) = A (left f) s

-- instance (Arrow a) => ArrowTransformer A a where
--     lift a = A a 0

Размер по умолчанию всегда должен быть равен 0, чтобы соответствовать законам. Например, id должен иметь размер 0, как и x . id === x, благодаря закону arr id === id мы имеем, что arr f также должен иметь размер 0 и т. д.

Но мы можем определить пользовательскую функцию, которая присваивает заданный размер базовой стрелке:

sized :: Int -> a b c -> A a b c
sized = flip A

Для примера построим несколько стрелок типа A (->). То есть лежащие в основе стрелки — это просто функции.

-- * Example (adapted from https://wiki.haskell.org/Arrow_tutorial)

-- | Both 'f' and 'g' are constructed to have a size of 1.
f, g :: A (->) Int Int
f = sized 1 $ arr (`div` 2)
g = sized 1 $ arr (\x -> x*3 + 1)

h :: A (->) Int Int
h = proc x -> do
      fx <- f -< x
      gx <- g -< x
      returnA -< (fx + gx)

Вы можете запустить h, например, как runA h 5. Но вы также можете измерить его размер с помощью sizeA h, что, как и ожидалось, возвращает 2. Обратите внимание, что вам не нужно запускать стрелку, чтобы получить ее размер. Вы можете представить его в виде схемы, и вам не нужно на самом деле включать схему, чтобы просто увидеть ее размер.

Обратите внимание, что мы не можем сделать это для монады, поэтому у нас не может быть экземпляра ArrowChoice A. В монаде мы можем вычислить следующий «эффект» из предыдущего результата, а это значит, что мы никогда не сможем вычислить размер без фактического выполнения монадического вычисления.