A CPS question and answer

Continuation passing style is a hard concept. Recently one fellow pasted the following piece of Haskell code in IRC and asked for its meaning:

cfold’ f z [] = z
cfold’ f z (x:xs) = f x z (\y -> cfold’ f y xs)

cfold f z l = cfold’ (\x t g -> f x (g t)) z l

It is a fold implemented in continuation passing style. Let's see what we can say about the type of cfold'. The function cfold' takes a function f of three arguments. The first argument of f is of some type t, the second argument is of some type t1, and the third argument is another function. The other function takes one argument of type t1 and its return value is the same as cfold's, that is, t1. Finally the return type of f is t1 as well. The second argument z of cfold' is something of type t1. The third argument of cfold' is a list of ts that is pattern matched in the definitions of cfold'. Thus, the type signature of the whole function is cfold' :: (t -> t1 -> (t1 -> t1) -> t1) -> t1 -> [t] -> t1.

Next, what can we say about the definition of cfold'? When the third argument, that is a list, is an empty list, it returns what ever is the value of its second argument of type t1. If the list is non-empty, we return what is returned by calling f when it is given x -- the head of the list (of type t), then z of type t1, and a function from t1 to t1.

At this point we start calling the first argument of cfold', that is f, a continuation. In the second definition of cfold' the control is passed to a continuation f. The continuation is a recipe of what to do next. The continuation is given the head of the list and a base value for the fold. The trailing anonymous function from t1 to t1 allows the continuation to get the result of the fold for the tail of the list.

Now, given the fold implemented in CPS, how do we, for example, multiply the elements of a list together? The continuation must contain that logic. Our continuation was a function of type (t -> t1 -> (t1 -> t1) -> t1). The first argument was the head of the list, the second argument was the base value for the fold, and the third argument was the way to get result of the fold for the tail of the list. So the definition for the continuation must be something like this:

(\x t g -> (*) x (g t))

It says that given the head of the list, x, a base value for the fold, t, and the function g that yields the result of the fold for the tail of the list when it is given t, the result of the whole fold is the list head multiplied by the value of the fold for the list tail.

Now cfold' alone is not describing much. We define cfold that passes the continuation, that does the actual folding, to cfold'.

If we try cfold with the sum function, a base value of zero and a one element list containing the number one, the expression reduces as below:

cfold (+) 0 [1]
(\f z l -> cfold' (\x t g -> f x (g t)) z l) (+) 0 [1]
cfold' (\x t g -> (+) x (g t)) 0 [1]
(\f z (x:xs) -> f x z (\y -> cfold' f y xs)) (\x t g -> (+) x (g t)) 0 [1]
(\x t g -> (+) x (g t)) 1 0 (\y -> cfold' (\x t g -> (+) x (g t)) y [])
(+) 1 ((\y -> cfold' (\x t g -> (+) x (g t)) y []) 0)
(+) 1 0
1

So for a non-empty list, cfold' calls the continuation, that performs the folding, and for an empty list it returns the base value.