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

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