f# - recursivos - funciones recursivas ejemplos

¿Por qué esta función de secuencia F#no es recursiva?

Question

Divulgación: esto surgió en FsCheck, un marco de prueba aleatorio F # que mantengo. Tengo una solución, pero no me gusta. Además, no entiendo el problema, simplemente fue eludido.

Una implementación bastante estándar de la secuencia (monádica, si vamos a usar palabras grandes) es:

let sequence l = 
    let k m m'' = gen { let! x = m
                       let! xs = m''
                       return (x::xs) }
    List.foldBack k l (gen { return [] })

Donde gen puede ser reemplazado por un generador de cómputo de elección. Lamentablemente, esa implementación consume espacio en la pila y, por lo tanto, finalmente la pila se desborda si la lista es lo suficientemente larga. La pregunta es: ¿por qué? Sé que, en principio, foldback no es recursivo de cola, pero los conejitos inteligentes del equipo de F # han eludido eso en la implementación de foldback. ¿Hay algún problema en la implementación del generador de cómputo?

Si cambio la implementación al siguiente, todo está bien:

let sequence l =
    let rec go gs acc size r0 = 
        match gs with
        | [] -> List.rev acc
        | (Gen g)::gs'' ->
            let r1,r2 = split r0
            let y = g size r1
            go gs'' (y::acc) size r2
    Gen(fun n r -> go l [] n r)

Para completar, el generador de compilación y el tipo de generador se pueden encontrar en la fuente FsCheck

Answer 1

Estás en lo cierto: la razón por la que obtienes un desbordamiento de pila es que la operación de vinculación de la mónada debe ser recursiva de cola (porque se usa para agregar valores durante el plegado).

La mónada utilizada en FsCheck es esencialmente una mónada de estado (mantiene el generador actual y algunos números). Lo simplifiqué un poco y obtuve algo así como:

type Gen<''a> = Gen of (int -> ''a)

let unit x = Gen (fun n -> x)

let bind k (Gen m) = 
    Gen (fun n -> 
      let (Gen m'') = k (m n) 
      m'' n)

Aquí, la función de bind no es recursiva de cola porque llama a k y luego hace algo más de trabajo. Puede cambiar la mónada para que sea una mónada de continuación . Se implementa como una función que toma el estado y una continuación , una función que se llama con el resultado como argumento. Para esta mónada, puedes hacer bind tail recursive:

type Gen<''a> = Gen of (int -> (''a -> unit) -> unit)

let unit x = Gen (fun n f -> f x)

let bind k (Gen m) = 
    Gen (fun n f -> 
      m n (fun r -> 
        let (Gen m'') = k r
        m'' n f))

El siguiente ejemplo no se superpone a la pila (y lo hizo con la implementación original):

let sequence l = 
  let k m m'' = 
    m |> bind (fun x ->
      m'' |> bind (fun xs -> 
        unit (x::xs)))
  List.foldBack k l (unit [])

let (Gen f) = sequence [ for i in 1 .. 100000 -> unit i ]
f 0 (fun list -> printfn "%d" list.Length)

Answer 2

Sobre la base de la respuesta de Tomás, vamos a definir dos módulos:

module Kurt = 
    type Gen<''a> = Gen of (int -> ''a)

    let unit x = Gen (fun _ -> x)

    let bind k (Gen m) =     
        Gen (fun n ->       
            let (Gen m'') = k (m n)       
            m'' n)

    type GenBuilder() =
        member x.Return(v) = unit v
        member x.Bind(v,f) = bind f v

    let gen = GenBuilder()


module Tomas =
    type Gen<''a> = Gen of (int -> (''a -> unit) -> unit)

    let unit x = Gen (fun _ f -> f x)

    let bind k (Gen m) =     
        Gen (fun n f ->       
            m n (fun r ->         
                let (Gen m'') = k r        
                m'' n f))

    type GenBuilder() =
        member x.Return v = unit v
        member x.Bind(v,f) = bind f v

    let gen = GenBuilder()

Para simplificar un poco las cosas, reescribamos su función de secuencia original como

let rec sequence = function
| [] -> gen { return [] }
| m::ms -> gen {
    let! x = m
    let! xs = sequence ms
    return x::xs }

Ahora, la sequence [for i in 1 .. 100000 -> unit i] se ejecutará hasta su finalización independientemente de si la sequence se define en términos de Kurt.gen o Tomas.gen . El problema no es que la sequence cause un desbordamiento de la pila al usar sus definiciones, sino que la función devuelta desde la llamada a la sequence causa un desbordamiento de la pila cuando se la llama.

Para ver por qué esto es así, expandamos la definición de sequence en términos de las operaciones monádicas subyacentes:

let rec sequence = function
| [] -> unit []
| m::ms ->
    bind (fun x -> bind (fun xs -> unit (x::xs)) (sequence ms)) m

Alineando los valores de Kurt.unit y Kurt.bind y simplificando como locos, obtenemos

let rec sequence = function
| [] -> Kurt.Gen(fun _ -> [])
| (Kurt.Gen m)::ms ->
    Kurt.Gen(fun n ->
            let (Kurt.Gen ms'') = sequence ms
            (m n)::(ms'' n))

Ahora está claro por qué llamar a let (Kurt.Gen f) = sequence [for i in 1 .. 1000000 -> unit i] in f 0 desborda la pila: f requiere una llamada no recursiva para secuenciar y evaluar el función resultante, por lo que habrá un marco de pila para cada llamada recursiva.

Al incluir Tomas.unit y Tomas.bind en la definición de sequence , obtenemos la siguiente versión simplificada:

let rec sequence = function
| [] -> Tomas.Gen (fun _ f -> f [])
| (Tomas.Gen m)::ms ->
    Tomas.Gen(fun n f ->  
        m n (fun r ->
            let (Tomas.Gen ms'') = sequence ms
            ms'' n (fun rs ->  f (r::rs))))

Razonar acerca de esta variante es complicado. Puedes verificar empíricamente que no volará la pila para algunas entradas arbitrariamente grandes (como muestra Tomás en su respuesta), y puedes pasar por la evaluación para convencerte de este hecho. Sin embargo, el consumo de la pila depende de las instancias Gen en la lista que se transfiere, y es posible volar la pila para las entradas que no son recursivas por la cola:

// ok
let (Tomas.Gen f) = sequence [for i in 1 .. 1000000 -> unit i]
f 0 (fun list -> printfn "%i" list.Length)

// not ok...
let (Tomas.Gen f) = sequence [for i in 1 .. 1000000 -> Gen(fun _ f -> f i; printfn "%i" i)]
f 0 (fun list -> printfn "%i" list.Length)