Какая общая структура имеет этот тип?

При взломе чего-то ранее, я создал следующий код:

newtype Callback a = Callback { unCallback :: a -> IO (Callback a) }

liftCallback :: (a -> IO ()) -> Callback a
liftCallback f = let cb = Callback $ \x -> (f x >> return cb) in cb

runCallback :: Callback a -> IO (a -> IO ())
runCallback cb =
    do ref <- newIORef cb
       return $ \x -> readIORef ref >>= ($ x) . unCallback >>= writeIORef ref

Callback a представляет собой функцию, которая обрабатывает некоторые данные и возвращает новый обратный вызов, который должен использоваться для следующего уведомления. Обратный вызов, который может в основном заменить себя, так сказать. liftCallback просто поднимает нормальную функцию к моему типу, а runCallback использует IORef для преобразования a Callback в простую функцию.

Общая структура типа:

data T m a = T (a -> m (T m a))

Похоже, что это может быть изоморфно некоторой известной математической структуре теории категорий.

Но что это? Это монада или что-то еще? Аппликативный функтор? Трансформированная монада? Стрела, даже? Есть ли подобная поисковая система Hoogle, которая позволяет мне искать общие шаблоны, подобные этому?

Ответ 1

Термин, который вы ищете, это бесплатный трансформатор монады. Лучшее место, чтобы узнать, как эта работа заключается в том, чтобы прочитать статью "Трубы Coroutine" в вопрос 19 "The Monad Reader" . Марио Блажевич дает очень ясное описание того, как работает этот тип, за исключением того, что он называет его "коротинским" типом.

Я написал свой тип в пакете transformers-free, а затем он был объединен в пакет free, который является его новым официальным домом.

Тип Callback изоморфен:

type Callback a = forall r . FreeT ((->) a) IO r

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

Free ((->) a) r

Это будет синтаксическое дерево, которое принимает ноль или более a в качестве входных данных, а затем возвращает значение r.

Однако обычно мы хотим внедрить эффекты или сделать следующий шаг дерева синтаксиса зависимым от какого-либо эффекта. Чтобы сделать это, мы просто продвигаем нашу свободную монаду на бесплатный монадный трансформатор, который перемежает базовую монаду между шагами дерева синтаксиса. В случае вашего типа Callback вы чередуете IO между каждым шагом ввода, поэтому ваша базовая монада IO:

FreeT ((->) a) IO r

Хорошая вещь о свободных монадах состоит в том, что они автоматически являются монадами для любого функтора, поэтому мы можем воспользоваться этим, чтобы использовать нотацию do для сборки нашего дерева синтаксиса. Например, я могу определить команду await, которая свяжет вход в монаду:

import Control.Monad.Trans.Free

await :: (Monad m) => FreeT ((->) a) m a
await = liftF id

Теперь у меня есть DSL для записи Callback s:

import Control.Monad
import Control.Monad.Trans.Free

printer :: (Show a) => FreeT ((->) a) IO r
printer = forever $ do
    a <- await
    lift $ print a

Обратите внимание, что мне никогда не приходилось определять необходимый экземпляр Monad. Оба FreeT f и Free f автоматически Monad для любого функтора f, и в этом случае ((->) a) является нашим функтором, поэтому он автоматически делает правильные вещи. Это волшебство теории категорий!

Кроме того, нам не приходилось определять экземпляр MonadTrans, чтобы использовать lift. FreeT f автоматически является монадным трансформатором, заданным любым функтором f, поэтому он позаботился об этом и для нас.

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

feed :: [a] -> FreeT ((->) a) IO r -> IO ()
feed as callback = do
    x <- runFreeT callback
    case x of
        Pure _ -> return ()
        Free k -> case as of
            []   -> return ()
            b:bs -> feed bs (k b)

Фактическая печать происходит, когда мы привязываем runFreeT callback, который затем дает нам следующий шаг в дереве синтаксиса, который мы будем кормить следующим элементом списка.

Попробуйте:

>>> feed [1..5] printer
1
2
3
4
5

Однако вам даже не нужно писать все это самостоятельно. Как отметил Петр, в моей библиотеке pipes представлены общие потоковые шаблоны, подобные этому для вас. Ваш обратный вызов:

forall r . Consumer a IO r

Как мы можем определить printer с помощью pipes:

printer = forever $ do
    a <- await
    lift $ print a

... и мы можем подать ему список таких значений:

>>> runEffect $ each [1..5] >-> printer
1
2
3
4
5

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

Если вы хотите узнать больше о pipes, я рекомендую вам прочитать учебник.

Ответ 2

Общая структура типа выглядит мне как

data T (~>) a = T (a ~> T (~>) a)

где (~>) = Kleisli m в ваших терминах (стрелка).

Callback сам по себе не похож на экземпляр любого стандартного класса Haskell, о котором я могу думать, но это контравариантный функтор (также известный как Cofunctor, вводящий в заблуждение, как выясняется). Поскольку он не включен ни в одну из библиотек, которые поставляются с GHC, существует несколько определений этого в Hackage (использовать этот), но все они выглядят примерно так:

class Contravariant f where
    contramap :: (b -> a) -> f a -> f b
 -- c.f. fmap :: (a -> b) -> f a -> f b

Тогда

instance Contravariant Callback where
    contramap f (Callback k) = Callback ((fmap . liftM . contramap) f (f . k))

Существует ли еще какая-то экзотическая структура из теории категорий, которой обладает Callback? Я не знаю.

Ответ 3

Я думаю, что этот тип очень близок к тому, что я слышал, называемый "Circuit", который является типом стрелки. Игнорируя на мгновение IO-часть (поскольку мы можем это сделать, просто изменив стрелку Kliesli), трансформатор цепи:

newtype CircuitT a b c = CircuitT { unCircuitT :: a b (c, CircuitT a b c) }

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

Callback a ~=~ CircuitT (Kleisli IO) a ()

Как будто мы смотрим на правую сторону:

CircuitT (Kleisli IO) a () ~=~
  (Kliesli IO) a ((), CircuitT (Kleisli IO) a ()) ~=~
  a -> IO ((), CircuitT (Kliesli IO) a ())

И здесь вы можете увидеть, как это похоже на Callback a, за исключением того, что мы также выводим значение единицы. Поскольку значение единицы в кортеже с чем-то еще в любом случае, это действительно не говорит нам о многом, поэтому я бы сказал, что они в основном одинаковы.

N.B. По какой-то причине я использовал ~ = ~ для аналогичных, но не совсем эквивалентных. Они очень близки, хотя, в частности, обратите внимание, что мы могли бы преобразовать a Callback a в CircuitT (Kleisli IO) a () и наоборот.

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

Ответ 4

Просто наблюдение, ваш тип кажется весьма связанным с Consumer p a m, появляющимся в pipes (и, возможно, другие похожие либраты):

type Consumer p a = p () a () C
-- A Pipe that consumes values
-- Consumers never respond.

где C - пустой тип данных, а p - это экземпляр класса Proxy. Он потребляет значения типа a и никогда не производит никаких (поскольку его выходной тип пуст).

Например, мы могли бы преобразовать a Callback в Consumer:

import Control.Proxy
import Control.Proxy.Synonym

newtype Callback m a = Callback { unCallback :: a -> m (Callback m a) }

-- No values produced, hence the polymorphic return type `r`.
-- We could replace `r` with `C` as well.
consumer :: (Proxy p, Monad m) => Callback m a -> () -> Consumer p a m r
consumer c () = runIdentityP (run c)
  where
    run (Callback c) = request () >>= lift . c >>= run

См. учебник.

(Это должно быть скорее комментарий, но он слишком длинный.)