3

This question is about functional programming. The sample code is in F#.

Suppose I have a simple function f:

let f x = 
    x + 1

Now (for reasons I don't want to explain, related to threading) I must turn f into a function with continuations:

let f x cont =
    cont (x+1)

Now I must rewrite all functions that call f, which won't compile anymore.

For example, if I have this function

let g x =
   let res = f x
   res + 2

I must rewrite g as

let g x cont =
    f x (fun res ->
            cont (res + 2) )

This is becoming complicated already, but is still manaegable.

But the problem is: how do I rewrite the following piece of code?

let lmapped = [ for x in l do
                    let res = f x
                    yield res + 1 ]
if List.isEmpty lmapped then
   ...

is there a simple way to rewrite it? (Possibly avoiding an explicit recursive function, like "let rec ...") Thanks

2 Answers 2

8

Writing code using explicit continuation passing style gets ugly quite quickly.

In this case, you'd need to write continuation-based version of the List.map function:

let map f list cont = 
  let rec loop acc list cont = 
    match list with
    | [] -> cont (List.rev acc) // Reverse the list at the end & call continuation!
    | x::xs -> f x (fun x' ->   // Call `f` with `cont` that recursively calls `loop`
        loop (x'::acc) xs cont )// Call `loop` with newly projected element in `acc`
  loop [] list cont

In principle, this is just a "simple syntactic transformation" that can be done "automatically", but it is very hard to do this without getting lost!

The function is really just an ordinary map function with inner loop function that recursively iterates over the input list and calls f to do the projection. Except that all the functions take additional parameter cont and return result by calling cont at the end. This is also the case for the f function passed to map! See:

map (fun n cont -> cont (n * 2)) [1 .. 10] (printfn "%A")

If you're using continuations heavily, then it is perhaps easier to write computation builder (aka monad) for working with continuations. This does not quite fit in a single StackOverflow answer, but see this excellent post by Brian McNamara

0

So to answer the question using Tomas' map function:

first rewrite the code as

let lmapped = List.map
               (fun x ->
                   let res = f x
                   res + 1 )
               l
if List.isEmpty lmapped then
  ...

and then we can rewrite with continuations:

map
   (fun x cont ->
         f x (fun res ->
                 cont (res + 1 )))
   l
   (fun lmapped ->
        if List.isEmpty lmapped then

             ... 
        )

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.