如何编写 Continuation Monad 的 Functor 实例？

Question

如何编写 Continuation Monad 的 Functor 实例？

haskellcontinuationsquickcheckcontinuation-passing

4

newtype Cont k a = Cont { runCont :: (a -> k) -> k }

instance Functor (Cont k) where
  -- fmap :: (a -> b) -> (Cont k a) -> (Cont k b)
  fmap f (Cont akTok) = Cont $ ???

我的疑问：

我们只能为任何可以产生类型输出的数据类型编写 Functor 实例（例如：[a]、Maybe a、(y -> a)），但不能为消耗类型的数据类型编写，现在在上面的数据类型中它消耗了一个消耗 a 的函数，那么这种间接消耗如何被视为产生类型 a。这意味着我们不能为 (k -> a) -> k 写入 Functor 实例吗？
我该如何阅读 Cont 数据类型。当有 a 时，Cont 会产生 k 吗？（就像 JavaScript XHR 回调在从服务器获取响应后生成 JSON 一样？）
如何为 Cont 数据类型编写 QuickCheck 测试用例

import Test.QuickCheck
import Test.QuickCheck.Checkers
import Test.QuickCheck.Classes

newtype Cont k a = Cont { runCont :: (a -> k) -> k }

instance Functor (Cont k) where
   ...

instance Applicative (Cont k) where
   ...

instance Monad (Cont k) where
   ...

instance (Arbitrary a, Arbitrary b) => Arbitrary (Cont k a) where
    arbitrary = do
        -- akTok <- arbitrary -- How to generate Arbitrary functions like this
        return $ Cont akTok

instance (Eq k, Eq a) => EqProp (Cont k a) where
    (=-=) = eq -- How can I test this equality

main :: IO ()
main = do
    let trigger :: Cont ???
        trigger = undefined
    quickBatch $ functor trigger
    quickBatch $ applicative trigger
    quickBatch $ monad trigger

- Pawan Kumar

2

看一下Haskell维基百科关于continuations的章节——这是一个很好的介绍此主题的文章。 - bradrn

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Joseph Sible-Reinstate Monica · Accepted Answer

对于任何类型，最多只有一个有效的Functor，因此很容易进行机械求解。实际上，我们可以让编译器为我们完成这项艰巨的工作：

GHCi, version 8.6.5: http://www.haskell.org/ghc/  :? for help
Prelude> :set -ddump-deriv -XDeriveFunctor
Prelude> newtype Cont k a = Cont { runCont :: (a -> k) -> k } deriving(Functor)

==================== Derived instances ====================
Derived class instances:
  instance GHC.Base.Functor (Ghci1.Cont k) where
    GHC.Base.fmap f_a1xR (Ghci1.Cont a1_a1xS)
      = Ghci1.Cont
          ((\ b5_a1xT b6_a1xU
              -> (\ b4_a1xV -> b4_a1xV)
                   (b5_a1xT
                      ((\ b2_a1xW b3_a1xX
                          -> (\ b1_a1xY -> b1_a1xY) (b2_a1xW (f_a1xR b3_a1xX)))
                         b6_a1xU)))
             a1_a1xS)
    (GHC.Base.<$) z_a1xZ (Ghci1.Cont a1_a1y0)
      = Ghci1.Cont
          ((\ b6_a1y1 b7_a1y2
              -> (\ b5_a1y3 -> b5_a1y3)
                   (b6_a1y1
                      ((\ b3_a1y4 b4_a1y5
                          -> (\ b2_a1y6 -> b2_a1y6)
                               (b3_a1y4 ((\ b1_a1y7 -> z_a1xZ) b4_a1y5)))
                         b7_a1y2)))
             a1_a1y0)


Derived type family instances:


Prelude>

这很复杂，但很容易简化（只需重命名一些变量，删除一些基本上是 id 的函数，并使用 . 而不是手写）：

instance Functor (Cont k) where
  fmap f (Cont k2) = Cont (\k1 -> k2 (k1 . f))

考虑使用 Op，并利用它的 Contravariant 实例定义你的 Functor，这也许会更有启发性：

import Data.Functor.Contravariant

instance Functor (Cont k) where
  fmap f = Cont . getOp . contramap (getOp . contramap f . Op) . Op . runCont

或者更容易理解的是，通过一些扩展:

{-# LANGUAGE ScopedTypeVariables, TypeApplications #-}

import Data.Coerce
import Data.Functor.Contravariant

instance Functor (Cont k) where
  fmap f = coerce (contramap @(Op k) (contramap @(Op k) f))

或者完全放弃这种类型类，只需要注意它的 contramap = flip (.)：

instance Functor (Cont k) where
  fmap f = Cont . contramapFunc (contramapFunc f) . runCont
    where contramapFunc = flip (.)

这可行是因为双重反变函子会产生一个协变函子。

另一个选择是移除 newtype 封装，然后进行类型俄罗斯方块游戏：

instance Functor (Cont k) where
  fmap f = Cont . fmapRaw f . runCont
    where
      fmapRaw :: (a -> b) -> ((a -> k) -> k) -> (b -> k) -> k
      fmapRaw f k2 k1 = k2 (k1 . f)

在这里，我们有一个 a -> b，一个 (a -> k) -> k，以及一个 b -> k，我们需要将它们组合起来得到一个 k。如果我们将 b -> k 与 a -> b 组合起来，我们会得到一个 a -> k，然后将其提供给 (a -> k) -> k 就可以得到一个 k。