Evitar desbordamiento de pila (con F # secuencias infinitas de secuencias)

Question

Tengo este "código de aprendizaje" que escribió para la SEC Morris en F # que sufre de desbordamiento de pila que no sé cómo evitar. "Morris" devuelve una secuencia infinita de "ver y decir" secuencias (es decir, {{1}, {1,1}, {2,1}, {1,2,1,1}, {1,1,1 , 2,2,1}, {3,1,2,2,1,1}, ...}).

    let printList l =
        Seq.iter (fun n -> printf "%i" n) l
        printfn ""

    let rec morris s = 
        let next str = seq {
            let cnt = ref 1  // Stack overflow is below when enumerating
            for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do
                if cur.[0] <> cur.[1] then
                    yield!( [!cnt ; cur.[0]] )
                    cnt := 0
                incr cnt
        }
        seq {
        yield s
        yield! morris (next s) // tail recursion, no stack overflow
        }

    // "main"
    // Print the nth iteration
    let _ =  [1] |> morris |> Seq.nth 3125 |> printList 

Puede escoger de la iteración n-ésima utilizando Seq.nth pero sólo se puede llegar tan lejos antes de llegar a un desbordamiento de pila. La recursividad de un bit que tengo es la recursión de cola y, en esencia, construye un conjunto relacionado de los encuestadores. Eso no es donde está el problema. Es cuando "enumeración" se llama en el decir la secuencia número 4.000. Tenga en cuenta que es con F # 1.9.6.16, la versión anterior superó a cabo por encima de 14000). Esto se debe a la forma en que las secuencias unidas se resuelven. Las secuencias son perezosos y por lo que el "recursión" es perezoso. Es decir, ss ss n llama n-1, que llama a la SEC N-2 y así sucesivamente para obtener el primer artículo (el primer # es el peor de los casos).

Yo entiendo que [|0|] |> Seq.append str |> Seq.windowed 2, está haciendo que mi problema peor y podría triplicar el # pude generar si eliminé eso. En términos prácticos el código funciona lo suficientemente bien. La iteración 3125a de Morris sería más de 10 ^ 359 caracteres de longitud.

El problema que estoy tratando de resolver es cómo conservar el eval perezosos y tienen un ningún límite en función del tamaño de la pila para la iteración puedo escoger de. Busco el F # lenguaje adecuado para hacer el límite en función del tamaño de la memoria.

Actualizar octubre '10

Después de aprender F # un poco mejor, un poco de Haskell, pensando y la investigación de este problema desde hace más de año, por fin puedo responder a mi propia pregunta. Pero como siempre con problemas difíciles, el problema comienza con él que es la pregunta equivocada. El problema no es secuencias de secuencias - es realmente debido a una secuencia definida recursivamente. Mis conocimientos de programación funcionales son un poco mejor ahora y lo que es más fácil ver lo que está pasando con la versión más adelante, que todavía consigue un stackoverflow

let next str = 
    Seq.append str [0]
    |> Seq.pairwise
    |> Seq.scan (fun (n,_) (c,v) ->
            if (c = v) then (n+1,Seq.empty)
            else (1,Seq.ofList [n;c]) ) (1,Seq.empty)
    |> Seq.collect snd

let morris = Seq.unfold(fun sq -> Some(sq,next sq))

Eso basicially crea una cadena muy larga de la función de procesamiento de Sec llama para generar los sequnces. El módulo Sec que viene con F # es lo que no puede seguir la cadena sin necesidad de utilizar la pila. Hay una optimización que utiliza para la agregación y de secuencias definidas de forma recursiva, pero que la optimización sólo funciona si la recursión está implementando un append.

Así que esto va a funcionar

let rec ints n = seq { yield n; yield! ints (n+1) }
printf "%A" (ints 0 |> Seq.nth 100000);;

Y éste obtendrá un stackoverflow.

let rec ints n = seq { yield n; yield! (ints (n+1)|> Seq.map id) }
printf "%A" (ints 0 |> Seq.nth 100000);;

Para probar el F # libary estaba el tema, escribí mi propio módulo Sec que implementó añadir, por parejas, escanear y recoger usando continutions y ahora puedo empezar a generar e imprimir los siguientes 50.000 sin ningún problema (que nunca va a terminar ya que es más de 10 ^ 5697 dígitos de largo).

Algunas notas adicionales:

• Las continuaciones eran el idioma que estaba buscando, pero en este caso, tenían que ir a la biblioteca # F, no es mi código. Aprendí sobre continuaciones en F # de de Tomas Petricek Mundo Real programación funcional libro.
• La lista de respuestas perezoso que aceptaba sostenía el otro idioma; evaluación perezosa. En mi biblioteca reescrito, también tenía que aprovechar el tipo perezoso para evitar stackoverflow.
• La lista perezosa versión sorta de obras de suerte (tal vez por diseño, sino que está más allá de mi capacidad actual para determinar) - la activa-coincidencia de patrones que utiliza mientras se está construyendo y la iteración hace que las listas para el cálculo de los valores antes de la recursividad requerida se pone demasiado de profundidad, por lo que es perezoso, pero no tan flojo que necesita continuaciones para evitar stackoverflow. Por ejemplo, en el momento de la segunda secuencia necesita un dígito desde la primera secuencia, que es ya ha sido calculado. En otras palabras, la versión LL no es estrictamente JIT perezosos para la generación de la secuencia, únicamente el administrador de la lista.

Answer 1

Se debería salir

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.PowerPack/Microsoft.FSharp.Collections.LazyList.html

pero voy a tratar de publicar una respuesta más completa más adelante.

Actualizar

Ok, una solución es a continuación. Representa la secuencia de Morris como LazyList de LazyLists de int, ya que supongo que usted quiere que sea perezoso en ambas direcciones ''.

El F # LazyList (en el FSharp.PowerPack.dll) tiene tres propiedades útiles:

• es perezoso (evaluación del enésimo elemento no ocurrirá hasta que se exige en primer lugar)
• que no vuelve a calcular (re-evaluación del elemento n-ésimo en la misma instancia de objeto no recalcular - es almacena en caché cada elemento después de que primero calcula)
• se puede 'olvidar' los prefijos (como 'cola' en la lista, el prefijo de referencia que ya no se encuentra disponible para la recolección de basura)

La primera propiedad es común con seq (IEnumerable), pero los otros dos son únicos a LazyList y muy útil para problemas de cálculo como el que se plantea en esta pregunta.

Sin más, el código:

// print a lazy list up to some max depth
let rec PrintList n ll =
    match n with
    | 0 -> printfn ""
    | _ -> match ll with
           | LazyList.Nil -> printfn ""
           | LazyList.Cons(x,xs) ->
               printf "%d" x
               PrintList (n-1) xs

// NextMorris : LazyList<int> -> LazyList<int>
let rec NextMorris (LazyList.Cons(cur,rest)) = 
    let count = ref 1
    let ll = ref rest
    while LazyList.nonempty !ll && (LazyList.hd !ll) = cur do
        ll := LazyList.tl !ll
        incr count
    LazyList.cons !count
        (LazyList.consf cur (fun() ->
            if LazyList.nonempty !ll then
                NextMorris !ll
            else
                LazyList.empty()))

// Morris : LazyList<int> -> LazyList<LazyList<int>>
let Morris s =
    let rec MakeMorris ll =
        LazyList.consf ll (fun () ->
            let next = NextMorris ll
            MakeMorris next
        )
    MakeMorris s

// "main"
// Print the nth iteration, up to a certain depth
[1] |> LazyList.of_list |> Morris |> Seq.nth 3125 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 3126 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 100000 |> PrintList 35
[1] |> LazyList.of_list |> Morris |> Seq.nth 100001 |> PrintList 35

Update2

Si lo que desea es contar, eso también está bien:

let LLLength ll =
    let rec Loop ll acc =
        match ll with
        | LazyList.Cons(_,rest) -> Loop rest (acc+1N)
        | _ -> acc
    Loop ll 0N

let Main() =
    // don't do line below, it leaks
    //let hundredth = [1] |> LazyList.of_list |> Morris |> Seq.nth 100
    // if we only want to count length, make sure we throw away the only
    // copy as we traverse it to count
    [1] |> LazyList.of_list |> Morris |> Seq.nth 100
        |> LLLength |> printfn "%A" 
Main()    

El uso de la memoria se mantiene plana (menos de 16M en mi caja) ... no ha terminado de ejecutarse todavía, pero lo calculado la longitud 55o rápido, incluso en mi caja lenta, por lo que creo que esto debería funcionar bien. Tenga en cuenta también que utilicé 'de bignum para la longitud, ya que creo que esto se desbordará un 'int'.

Answer 2

Creo que hay dos problemas principales aquí:

• La pereza es muy ineficiente por lo que se puede esperar una aplicación funcional perezoso para ejecutar órdenes de magnitud más lento. Por ejemplo, la implementación Haskell describe aquí es 2400 × más lento que el F # doy a continuación. Si desea una solución, lo mejor es, probablemente, para amortizar los cálculos por agrupamiento juntos en lotes ansiosos donde se producen los lotes bajo demanda.

• La función Seq.append es en realidad poniendo en código C # desde IEnumerable y, en consecuencia, su llamada de cola no quede eliminada y se escapa un poco más de espacio en la pila cada vez que vaya a través de él. Esto se muestra cuando se llega a enumerar más de la secuencia.

El siguiente es más de un 80 × más rápido que su aplicación en el cálculo de la longitud de la subsecuencia 50º, pero tal vez no es lo suficientemente vago para usted:

let next (xs: ResizeArray<_>) =
  let ys = ResizeArray()
  let add n x =
    if n > 0 then
      ys.Add n
      ys.Add x
  let mutable n = 0
  let mutable x = 0
  for i=0 to xs.Count-1 do
    let x' = xs.[i]
    if x=x' then
      n <- n + 1
    else
      add n x
      n <- 1
      x <- x'
  add n x
  ys

let morris =
  Seq.unfold (fun xs -> Some(xs, next xs)) (ResizeArray [1])

El núcleo de esta función es un pliegue sobre una ResizeArray que podría tenerse en cuenta y utiliza funcionalmente sin demasiada degradación del rendimiento si se ha utilizado una estructura como el acumulador.

Answer 3

Sólo tiene que guardar el elemento anterior que ha buscado.

let morris2 data = seq {
    let cnt = ref 0
    let prev = ref (data |> Seq.nth 0)

     for cur in data do
        if cur <> !prev then
            yield! [!cnt; !prev]
            cnt := 1
            prev := cur
        else
            cnt := !cnt + 1

    yield! [!cnt; !prev]
}

let rec morrisSeq2 cur = seq {
    yield cur
    yield! morrisSeq2 (morris2 cur)
}