Комплексное продолжение в 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

, где обновление обновляет состояние игры с заданным ходом, eval оценивает состояние игрыи возвращает инкремент (в настоящее время не используется) для инкрементальной оценки, а isTerminal оценивает, является ли позиция конечной позицией или нет.

Проблема заключается в том, что мне нужно зарегистрировать неизвестное количество действий (каждый оставшийся список.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 -> ... )

Я не уверен, что это даст вам заметное улучшение производительности. Я думаю, что продолжения в основном нужны, если у вас очень глубокая рекурсия (которая не помещается в стек). Если он помещается в стек, он, вероятно, будет работать быстро, используя стек.

Кроме того, переписывание в явный стиль продолжения делает программу немного уродливой. Вы можете улучшить это, используя выражение для работы с продолжениями. У Брайана есть сообщение в блоге на эту тему .