将函数转换为CPS

Question

我有以下until的CPS实现

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

哪种类型检查正常！现在，尝试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中重写时，continuation将获取结果，因此，如果您编写预期类型的map函数，您将拥有：

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

因此，continuation将结果列表作为参数。如果你看一下你的实现：

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