轉換功能，以CPS

Question

，我有以下CPS實施until：

until' p f x cc = p x (\y -> if y then cc(x) 
          else until' p f (f x (\z -> cc(z))) cc) 

哪種類型的檢查OK！現在，試圖CPS map：

map' f (x:xs) cc = f x (\y -> map f xs (\ys -> cc(y:ys))) 

另一種可能的實現：

map' f (x:xs) cc = cc(f x (\y cc' -> map f xs (\ys -> cc'(y:ys)))) 

但是他們沒有類型檢查。我在哪裏做錯了？

Couldn't match expected type ‘([a1] -> t2) -> t1’ 
       with actual type ‘[(a1 -> t1) -> t]’ 
    Relevant bindings include 
     y :: a1 (bound at test.hs:6:26) 
     cc :: [a1] -> t2 (bound at test.hs:6:15) 
     f :: a -> (a1 -> t1) -> t (bound at test.hs:6:6) 
     map' :: (a -> (a1 -> t1) -> t) -> [a] -> ([a1] -> t2) -> t 
     (bound at test.hs:6:1) 
    The function ‘map’ is applied to three arguments, 
    but its type ‘(a -> (a1 -> t1) -> t) -> [a] -> [(a1 -> t1) -> t]’ 
    has only two 
    In the expression: map f xs (\ ys -> cc (y : ys)) 
    In the second argument of ‘f’, namely 
     ‘(\ y -> map f xs (\ ys -> cc (y : ys)))’ 
Failed, modules loaded: none. 

Answer 1

當CPS改寫延續需要的結果，所以，如果你寫你的地圖功能的預期的類型，你有：

mapk :: (a -> b) -> [a] -> ([b] -> r) -> r 

所以需要延續的結果列表作爲參數。如果你看看你的實現：

map' f (x:xs) cc = f x (\y -> map f xs (\ys -> cc(y:ys))) 

y和ys應具有相同的類型（[b]），但是你想他們(:)結合一個希望將b和[b]。相反，你想要的東西，如：

mapk _ [] k = k [] 
mapk f (x:xs) k = mapk f xs (\rs -> k $ (f x):rs) 

Answer 2

這是一個錯字上

map' f (x:xs) cc = f x (\y -> map f xs (\ys -> cc(y:ys))) 

應該是：

map' f (x:xs) cc = f x (\y -> map' f xs (\ys -> cc(y:ys)))