logo标签列表

这种类型有什么一般的结构？

haskelltypeshigher-kinded-types
15

在之前的一次编写代码时，我创造了以下代码：

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 将 Callback 转换为简单函数。

类型的一般结构如下：

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

看起来这个结构可能与范畴论中一些著名的数学结构同构。

但它是什么？它是单子或者其他什么东西吗？是转换后的单子吗？甚至是箭头吗？是否有类似于Hoogle的搜索引擎，让我可以搜索这样的通用模式？

1
我会称之为“单子共流”，但这有点个人特色。 - sclv
单子共流听起来不错 :-) - Joachim Breitner
1
这让我想起了 Free -- Free f a = Either a (f (Either a (f (Either a (f ...) -- 和 Cofree -- Cofree f a = (a, f (a, f (a, f ...)，只不过用 (->) 代替了和/积。所以 T f a = a -> f (a -> f (a -> f ...，这使它是逆变的，与其他两个不同。 - shachaf
1
（由于 (->) 不是可交换的，您还可以获得 newtype Bar f a = Bar { unBar :: f (Bar f a) -> a }，当 f 是 Contravariant 时，它是一个 Functor，而不是相反。） - shachaf
4个回答
14
您要查找的术语是自由单子变换器。学习这些内容的最佳方式是阅读The Monad Reader第19期中的“协程管道”文章。Mario Blazevic非常清晰地描述了这种类型的工作原理，但他将其称为“Coroutine”类型。
我在transformers-free软件包中编写了他的类型，然后它被合并到free软件包中，这是它的新官方主页。
您的Callback类型是同构的：
type Callback a = forall r . FreeT ((->) a) IO r

为了理解自由单子变换器，您需要首先理解自由单子，它们只是抽象语法树。您给自由单子一个定义语法树中单个步骤的函子，然后它从该函子创建一个Monad，该Monad基本上是这些类型步骤的列表。因此，如果您有：
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。
import Control.Monad
import Control.Monad.Trans.Free

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

请注意，我从未必须定义必要的Monad实例。对于任何函子f，FreeT f和Free f都自动成为Monad，在这种情况下，((->) 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回调" 时，它给了我们语法树中的下一步，然后我们将其提供给列表的下一个元素。
让我们试试：
>>> feed [1..5] printer
1
2
3
4
5

然而，你甚至不需要自己编写所有这些内容。正如Petr所指出的，我的pipes库为您抽象了这种常见的流模式。你的回调函数只需是:

forall r . Consumer a IO r

使用 pipes 定义 printer 的方式是：

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

...我们可以像这样向其提供值列表：

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

我设计了pipes以涵盖各种流抽象，使您始终可以使用do符号来构建每个流组件。此外，pipes还提供了许多优雅的解决方案，例如状态和错误处理，以及双向信息流。因此，如果您将Callback抽象公式化为pipes，您可以免费使用大量有用的机制。
如果您想了解更多关于pipes的内容，我建议您阅读本教程。
哇，这是一个绝妙的答案！非常感谢，我可能需要一段时间来理解这一切。 - Niklas B.
8

这个类型的一般结构我觉得像是

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是否拥有一些来自范畴论的更为奇特的结构。
获取Cofunctor的正确方法是从contravariant包中获取。而且正确的做法是不要称其为cofunctor，因为“co”也可以表示“covariant”。http://hackage.haskell.org/packages/archive/contravariant/0.3/doc/html/Data-Functor-Contravariant.html - sclv
今天我学到了一些东西，很好。我将编辑我的答案中的名称。如果有其他非范畴论者想知道“协变函子”是什么：它只是一个普通的函子。 - dave4420
@sclv 我认为不叫它“cofunctor”的更好理由是，函子的对偶概念也是函子...我想... - jberryman
它们都是很好的理由，而且一起更是一个更好的理由。 - sclv
6

我认为这种类型非常接近我听过的被称为“电路”的箭头类型。暂时忽略 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 ())

从这里可以看出，它与回调函数a非常相似，只是我们还输出了一个单位值。由于单位值已经与其他内容在元组中，所以这并没有告诉我们太多，因此我认为它们基本上是一样的。

N.B. 我用“~=~”表示类似但不完全等同的意思，不知为什么。它们非常相似，特别要注意的是，我们可以将Callback a转换为CircuitT (Kleisli IO) a()，反之亦然。

编辑：我也完全同意这些想法：A）这是一个单子共流（期望无限数量的值的单子操作，我想这意味着）; B）一个只消耗管道（在许多方面与没有输出的电路类型非常相似，或者说将输出设置为()，因此这样的管道也可能具有输出）。

我认为它们是“完全相同的”（如果(a,()) = a成立的话，它们将是完全相同的（元组不是真正的乘积，但大多数情况下假装它们是可以的）。 - Philip JF
这也是我的感觉，如果 () 的唯一值是 ()，那么它们将完全相同，但当然 undefined 也是 () 类型的。 - user1020786
我非常喜欢这个答案。碰巧，就在几天前，我在一个与箭头相关的教程中遇到了Circuit类型，但已经忘记它了。我认为与sink / consumer的相似之处是最重要的，因为现在我想起来，我使用这个东西实际上是用来处理一系列“a”的 :) - Niklas B.
3

仅仅是一个观察，你的类型似乎与Consumer p a m在pipes库（以及可能其他类似的库）中出现的相关性很大：

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

其中C是一个空数据类型，p是Proxy类型类的一个实例。它消耗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

请查看教程。

(这本应该是一条评论，但有点太长了。)

是的，仔细想想，这很有道理。我基本上是在使用它来处理一系列“a”的流。 - Niklas B.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接