CODEWITHSUNDEEP
haskellfunctional-programmingpattern-matchingmonadscps
Mr. T
Mr. T

Reputation: 53

how to converting function to cps recursively

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

Upvotes: 3

Views: 225

Answers (2)

K. A. Buhr
K. A. Buhr

Reputation: 50884

Update: Ed'ka's answer shows how this can be done by evaluating a type family-based test in an instance context, but I'll leave the rest of my answer in place, since I think it's still relevant.

I think 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)

Upvotes: 2

Ed'ka
Ed'ka

Reputation: 7138

Here is an example of implementation of cpsRec which works for a function with any number of arguments:

{-# 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 (+))

Upvotes: 2

Related Questions