Continuación Complejo en Fa #

Question

todos los tutoriales de continuación que podemos encontrar son en continuaciones de longitud fija (es decir, la estructura de datos tiene un número conocido de artículos ya que está siendo atravesado

Me estoy poniendo en práctica depthFirstSearch negamax (http: // en .wikipedia.org/wiki/negamax) y mientras que el código funciona, me gustaría volver a escribir el código usando continuaciones

el código que tengo es el siguiente

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 

la actualizará cuando actualiza un gamestate con un con un movimiento dado, eval evalúa el estado del juego y r crea un incremento (actualmente no utilizado) para la evaluación incremental y esTerminal evalúa si la posición es o no una posición final.

El problema es que tengo que registrar un número desconocido de acciones (cada iteración list.map restante) a la continuación, y realmente no puedo concebir una forma eficiente de hacerlo.

Dado que este es un algoritmo exponencial, obviamente estoy buscando mantener esto tan eficiente como sea posible (aunque mi cerebro daña tratando de resolver esto nuestra, por lo que sí quiero la respuesta más de un uno eficiente)

Gracias

Answer 1

Creo que tendrá que implementar una versión basada en continuación de List.map para hacer esto. Una implementación estándar de map (usando el argumento acumulador) tiene el siguiente aspecto:

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

Si agrega un continuación como un argumento y transformar el código de retorno a través de una continuación, que obtendrá (la interesante caso es la rama x::xs en la función loop, donde primero llamamos f usando llamada final con un poco de continuidad como argumento):

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 

con lo que podrá normales List.map en una versión basada en continuación como esta:

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

No estoy seguro de si esto le dará una mejora notable en el rendimiento. Creo que las continuidades son necesarias principalmente si tienes una recursividad muy profunda (eso no cabe en la pila). Si encaja en la pila, entonces probablemente se ejecutará rápidamente usando la pila.

Además, la reescritura en el estilo de continuación explícito hace que el programa sea un poco feo. Puede mejorar eso usando una expresión de cálculo para trabajar con continuaciones. Brian tiene un blog post on this very topic.