情结延续

Question

所有延续教程我能看到的是在固定长度的延长体（即数据结构具有已知的一些项目，因为它正在走过

我实现深度优先搜索Negamax（HTTP：// EN .wikipedia.org /维基/ 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评估游戏状态和r会产生一个增量值（当前未使用）用于增量评估，isTerminal会评估该位置是否为结束位置。

问题是我必须注册未知数量的动作（每个剩余的list.map迭代）才能继续，而实际上我无法想象这样做的有效方式。

因为这是一个指数算法，我显然希望保持这种尽可能高效（虽然我的大脑好痛试图弄清楚这是我们的，所以我想要的答案不是一个有效率的多）

谢谢

Answer 1

我认为您需要实施List.map的延续版本来执行此操作。 的标准实现的map（使用蓄能器参数）看起来是这样的：

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

如果添加延续作为参数和改造码通过继续回来，你会得到（有趣情况是在loop功能，在这里我们首先使用尾部调用一些延续作为参数）调用f的x::xs分支：

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 

然后你就可以把正常List.map转化为这样的延续版本：

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

我不确定这是否会给您带来任何显着的性能提升。如果你有很深的递归（不适合堆栈），我认为主要需要延续。如果它适合堆栈，那么它可能会使用堆栈快速运行。

此外，重写为明确的延续风格使得程序有点难看。通过使用计算表达式来处理延续，可以改善这一点。 Brian有一个blog post on this very topic。