haskell - Haskell CPS: How to implement map and filter functions using Cont monad?

Question

I've been trying to learn CPS, seems I didn't really get my head around it, could you implement basic filter and map using Cont monad?

Answer 1

要做到这一点，让我们首先不使用 monad，因为 CPS 不依赖于它。

cpsMap :: (a -> b) -> [a] -> ([b] -> r) -> r
cpsMap f (a:as) c = cpsMap f as (c.(f a:))
cpsMap  _ []    c = c []

map' f xs = cpsMap f xs id

现在Cont单子是微不足道的

contMap :: (a -> b) -> [a] ->  Cont r [b]
contMap f (a:as) = contMap f as >>= return . (f a :)
contMap _ [] = return []

map'' f xs = runCont (contMap f xs) id

这里唯一的区别是我们不必自己接触延续，return为我们将值传递给它。

为了可视化它，让我们用map'' (+1) [1..3]

as      | c
[1,2,3] | id
[2,3]   | id . (2 :)
[3]     | id . (2 :) . (3 :)
[]      | id . (2 :) . (3 :) . (4 :)
id . (2 :) . (3 :) . (4 :) $ []
[2, 3, 4]

请注意，所做的只是将我们的代码部分Cont包装在一个新类型下。([b] -> r) -> r真的我们可以认为Cont是

newtype Cont r a = Cont ((a -> r) -> r)

我将把实施过滤器留给你:)