f# - F# 中的复杂延续

Question

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

我正在实现 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 迭代)，实际上我无法想象一种有效的方法来做到这一点。

由于这是一个指数算法，我显然希望尽可能保持它的效率(尽管我的大脑在试图计算出我们的结果时很受伤，所以我确实想要答案而不是一个有效的答案)

谢谢

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

如果你添加一个延续作为参数并将代码转换为通过延续返回，你会得到(有趣的情况是 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

然后就可以正常转 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 -> ... )

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

此外，对显式延续风格的重写使程序有点难看。您可以通过使用计算表达式来处理延续来改进这一点。布莱恩有一个 blog post on this very topic .