如何编写 Continuation Monad 的 Functor 实例？

Question

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 $ ???

我的疑惑：

1. 我们只能将 Functor 实例写入任何可以产生类型输出的数据类型（例如：[a], Maybe a, (y -> a)），但不能用于消耗类型的数据类型。现在，在上述数据键入它消耗了功能消耗一个那么这如何间接消耗的可视为生产型一个。这意味着我们不能为(k -> a) -> k编写 Functor 实例？

2. 如何读取Cont数据类型。续产生ķ时，它有一个？（就像 Javascript XHR 回调在从服务器获取数据时生成 JSON 一样？）

3. 如何为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

Answer 1

由于至多有一个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并Functor根据其Contravariant实例定义您的内容也可能很有启发性：

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)

在这里，我们有 an a -> b、 an(a -> k) -> k和 a b -> k，我们需要将它们组合起来得到 a k。如果我们将 theb -> k与 the 组合a -> b，我们得到 an a -> k，然后我们可以将它交给 the(a -> k) -> k以得到 a k。