如何递归地将函数转换为CPS。

Question

我想要将cpsRec定义如下，但我无法做到：

如果您有实现的想法，请告诉我。

import Control.Monad.Trans.Cont (Cont)

type family ContRec r x where
  ContRec r (a -> b) = a -> ContRec r b
  ContRec r a = Cont r a

cpsRec :: (a -> b) -> (a -> ContRec r b)
cpsRec f a =
  let fa = f a
   in case fa of
        (x -> y) -> cpsRec fa -- error!
        _ -> pure fa -- error!

-- use case
addT :: Int -> Int -> Int -> Int
addT x y z = x + y + z

addCpsT :: Int -> Int -> Int -> Cont r Int
addCpsT = cpsRec addT

- Mr. T

---

请包含编译错误的实际文本。 -- error！ 毫无描述性，这意味着任何潜在的问题回答者都必须决定是否值得花时间查看您所看到的错误消息。 - amalloy

Answer 1

更新： Ed'ka的答案展示了如何通过在实例上下文中评估基于类型族的测试来完成此操作，但我会保留我的回答，因为我认为它仍然相关。

我认为最合理的方法是为不同的元数定义cpsRec函数族：

cpsRec0 :: b -> Cont r b
cpsRec0 = pure

cpsRec1 :: (a1 -> b) -> a1 -> Cont r b
cpsRec1 f a = cpsRec0 (f a)

cpsRec2 :: (a1 -> a2 -> b) -> a1 -> a2 -> Cont r b
cpsRec2 f a = cpsRec1 (f a)

cpsRec3 :: (a1 -> a2 -> a3 -> b) -> a1 -> a2 -> a3 -> Cont r b
cpsRec3 f a = cpsRec2 (f a)

或者完全不使用辅助程序，直接执行转换。一旦你看到这种模式，就可以轻松地为任何你想要的参数函数编写代码：

import Control.Monad.Trans.Cont (Cont, cont)

addCpsT :: Int -> Int -> Int -> Cont r Int
addCpsT x y z = cont ($ addT x y z)

lengthCps :: [a] -> Cont r Int
lengthCps x = cont ($ length x)

zeroCps :: Num a => Cont r a
zeroCps = cont ($ 0)

- K. A. Buhr

---

谢谢您的回复。 最后一个例子是我最喜欢的。 - Mr. T

Answer 2

下面是一个实现cpsRec的例子，它适用于任意数量的参数：

{-# LANGUAGE DataKinds             #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE TypeFamilies          #-}
{-# LANGUAGE UndecidableInstances  #-}

import Control.Monad.Trans.Cont (Cont)
import Data.Proxy (Proxy(..))

-- | Helper type function to distinguish function from non-function
type family IsFun a where
  IsFun (a -> b) = 'True
  IsFun a = 'False

-- | Helper type class which includes auxiliary lifted Bool type parameter
class GContRec (i :: Bool) a rs where
  gcpsRec :: Proxy i -> a -> rs

-- | Intermediate recursive case: for a function `a -> b` (when `IsFun == True`)
instance (GContRec (IsFun b) b rs', (a -> rs') ~ rs) => GContRec 'True (a -> b) rs where
  gcpsRec _ f = gcpsRec (Proxy :: Proxy (IsFun b)) . f

-- | Base recursive case: not a function (`IsFun == False`) i.e. last argument - lift it to `Cont t a`
instance GContRec 'False a (Cont r a) where
  gcpsRec _ = pure

-- | Type class which defines very "generic" `cpsRec` without auxiliary type parameter
class ContRec a rs where
  cpsRec :: a -> rs

-- | Our implementation of `cpsRec` for `Cont`
instance (GContRec (IsFun a) a rs) => ContRec a rs where
  cpsRec = gcpsRec (Proxy :: Proxy (IsFun a))


-- Works for functions with any number of arguments
notCpsT :: Bool -> Cont r Bool
notCpsT = cpsRec not 

addT :: Int -> Int -> Int -> Int
addT x y z = x + y + z

addCpsT :: Int -> Int -> Int -> Cont r Int
addCpsT = cpsRec addT

foldrCpsT :: Int -> [Int] -> Cont r Int
foldrCpsT = cpsRec (foldr (+))

- Ed'ka