To do this, let's first start without the monad since CPS isn't dependent on it.
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
And now the Cont
monad is trivial
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
The only difference here is we don't have to touch the continuations ourselves, return
pipes the value into it for us.
To visualize it let's trace it with 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]
Notice that all Cont
does is wrap the ([b] -> r) -> r
part of our code under a newtype. Really we can think of Cont
as
newtype Cont r a = Cont ((a -> r) -> r)
I'll leave implementing filter to you :)