7

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

我正在实现 DepthFirstSearch Negamax(http://en.wikipedia.org/wiki/Negamax)，虽然代码有效，但我想使用延续重写代码

我的代码如下

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

其中 update 使用给定的移动更新游戏状态， eval 评估游戏状态并返回一个增量器（当前未使用）用于增量评估， isTerminal 评估该位置是否为结束位置。

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

由于这是一个指数算法，我显然希望尽可能地保持它的效率（虽然我的大脑在试图弄清楚这个是我们的，所以我确实想要答案而不是一个有效的答案）

谢谢

4

1 回答 1

5

我认为你需要实现一个基于延续的版本List.map来做到这一点。（使用 accumulator 参数）的标准实现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

如果您添加一个延续作为参数并将代码转换为通过延续返回，您将得到（有趣的情况是函数中的x::xs分支loop，我们首先f使用带有一些延续作为参数的尾调用进行调用）：

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

然后，您可以将 normalList.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 -> ... )

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

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

于 2011-05-10T02:42:12.790 回答