how to converting function to cps recursively-CodePudding

i'd like to define cpsRec as follows but i couldn't.

please let me know if you come up with ideas for implementation.

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

CodePudding user response：

These questions tend to stick around because most Haskellers aren't willing to step up and say some type-level trick is impossible, but I'll go out on a limb and say it...

You basically can't, unless you're willing to mark the final return value of addT with a sentinel type, like:

newtype Value a = Value a

addT :: Int -> Int -> Int -> Value Int
addT x y z = Value $ x   y   z

or define instances of a type class for every possible return type (e.g., once instance for Int to support addT, another for -- say -- Double, etc).

I know this isn't what you want to hear, but the most reasonable approach is to just define a family of cpsRec functions for different arities:

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)

or dispense with the cpsRec helper entirely and just perform the conversion directly. Once you've seen the pattern, it's easy to bang it out for any arity function you want:

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)