Complex Continuation in F#

Question

All of the continuation tutorials I can find are on fixed length continuations(i.e. the datastructure has a known number of items as it is being traversed

I am implementing DepthFirstSearch Negamax(http://en.wikipedia.org/wiki/Negamax) and while the code works, I would like to rewrite the code using continuations

the code I have is as follows

let naiveDFS driver depth game side = 
    List.map (fun x ->  
        //- negamax depth-1 childnode opposite side
        (x, -(snd (driver (depth-1) (update game x) -side)))) 
                                (game.AvailableMoves.Force())
    |> List.maxBy snd



let onPlay game = match game.Turn with 
                  | Black -> -1
                  | White -> 1

///naive depth first search using depth limiter
let DepthFirstSearch (depth:int) (eval:Evaluator<_>) (game:GameState) : (Move * Score) =
    let myTurn = onPlay game

    let rec searcher depth game side =
        match depth with
        //terminal Node
        | x when x = 0 || (isTerminal game) -> let movescore = (eval ((),game)) |> fst
                                               (((-1,-1),(-1,-1)),(movescore * side))
        //the max of the child moves, each child move gets mapped to 
        //it's associated score
        | _ -> naiveDFS searcher depth game side

where update updates a gamestate with a with a given move, eval evaluates the game state and returns an incrementer(currently unused) for incremental evaluation and isTerminal evaluates whether or not the position is an end position or not.

The Problem is that I have to sign up an unknown number of actions(every remaining list.map iteration) to the continuation, and I actually can't conceive of an efficient way of doing this.

Since this is an exponential algorithm, I am obviously looking to keep this as efficient as possible(although my brain hurts trying to figure this our, so I do want the answer more than an efficient one)

Thanks

Answer 1

I think you'll need to implement a continuation-based version of List.map to do this. A standard implementation of map (using the accumulator argument) looks like this:

let map' f l = 
  let rec loop acc l =
    match l with 
    | [] -> acc |> List.rev
    | x::xs -> loop ((f x)::acc) xs
  loop [] l

If you add a continuation as an argument and transform the code to return via a continuation, you'll get (the interesting case is the x::xs branch in the loop function, where we first call f using tail-call with some continuation as an argument):

let contMap f l cont = 
  let rec loop acc l cont =
    match l with
    | [] -> cont acc |> List.rev
    | x::xs -> f x (fun x' -> loop (x'::acc) xs cont)
  loop [] l cont

Then you can turn normal List.map into a continuation based version like this:

// Original version
let r = List.map (fun x -> x*2) [ 1 .. 3 ]

// Continuation-based version
contMap (fun x c -> c(x*2)) [ 1 .. 3 ] (fun r -> ... )

I'm not sure if this will give you any notable performance improvement. I think continuations are mainly needed if you have a very deep recursion (that doesn't fit on the stack). If it fits on the stack, then it will probably run fast using stack.

Also, the rewriting to explicit continuation style makes the program a bit ugly. You can improve that by using a computation expression for working with continuations. Brian has a blog post on this very topic.