如何编写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]，也许是a，（y-> a）），但不能使用消耗类型的数据类型。现在，在上面的数据类型中，它使用了一个消耗a的函数，那么可以将此间接消耗视为如何产生类型a。这意味着我们不能为（（k-> a）-> k？

写Functor实例

2. 我如何读取Cont数据类型。 Cont具有a时会产生k吗？ （就像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，并根据其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 (.)

这是有效的，因为加倍的协变函子会产生协变函子。

还有另一个选择是删除新类型包装，然后只播放Tetris类型：

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

[这里，我们有一个

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。