haskell 如何将函数递归转换为cps

szqfcxe2  于 2022-11-14  发布在  其他
关注(0)|答案(2)|浏览(146)

我想定义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
g2ieeal7

g2ieeal71#

下面是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 (+))
xdnvmnnf

xdnvmnnf2#

  • 更新:* 艾德'ka的答案显示了如何通过在示例上下文中评估基于类型族的测试来完成这一点,但我将保留我的答案的其余部分,因为我认为它仍然是相关的。

我认为最合理的方法是为不同的arity定义一系列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)

或者完全不用cpsRec辅助器,直接执行转换。一旦你看到了这个模式,就很容易把它转换成你想要的任何arity函数:

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)

相关问题