F#中的复杂延续

Question

我能找到的所有延续教程都是固定长度的延续(即数据结构在遍历时具有已知数量的项目)

我正在实施DepthFirstSearch Negamax(http://en.wikipedia.org/wiki/Negamax),当代码工作时,我想用continuation重写代码

我的代码如下

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

更新使用给定移动更新游戏状态,eval评估游戏状态并返回增量(当前未使用)以进行增量评估,并且终端评估该位置是否为结束位置.

问题是我必须将未知数量的操作(每个剩余的list.map迭代)注册到延续,我实际上无法想到这样做的有效方法.

由于这是一个指数算法,我显然希望尽可能保持这种效率(尽管我的大脑很痛苦,试图将其设为我们的,所以我确实希望答案不仅仅是一个有效的答案)

谢谢

Answer 1

我认为你需要实现一个基于continuation的版本List.map才能做到这一点.map(使用accumulator参数)的标准实现如下所示:

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

如果你将一个continuation添加为一个参数并将代码转换为通过continuation返回,你将得到(有趣的情况是函数中的x::xs分支loop,我们首先f使用tail-call调用一些continuation作为参数):

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

然后你可以将normal List.map转换为基于continuation的版本,如下所示:

// 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 -> ... )

我不确定这是否会给你带来显着的性能提升.我认为如果你有一个非常深的递归(不适合堆栈),主要需要继续.如果它适合堆栈,那么它可能会使用堆栈快速运行.

此外,重写为显式延续风格使程序有点难看.您可以通过使用计算表达式来处理continuation来改进它.Brian有关于这个主题的博客文章.