Éviter le débordement de pile (avec des séquences infinies de séquences F #)

Question

J'ai ce "code d'apprentissage" que j'ai écrit pour le morris seq dans f # qui souffre d'un débordement de pile que je ne sais pas comment éviter. "morris" renvoie une séquence infinie de séquences "voir et dire" (ie, {{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 

Vous pouvez sélectionner la ième itération à l'aide de Seq.nth, mais vous ne pouvez vous en rendre si loin avant d'avoir atteint un débordement de pile. Le seul élément de récursion que j'ai est la récursion de la queue, qui constitue essentiellement un ensemble d'énumérateurs liés. Ce n'est pas où le problème est. C'est quand "enum" est appelé sur le dire la 4000e séquence. Notez que c'est avec F # 1.9.6.16, la version précédente a dépassé 14000). C'est parce que la façon dont les séquences liées sont résolues. Les séquences sont paresseuses et donc la "récursion" est paresseuse. C'est-à-dire, seq n appelle seq n-1 qui appelle seq n-2 et ainsi de suite pour obtenir le premier élément (le tout premier # est le pire des cas). Je comprends que [|0|] |> Seq.append str |> Seq.windowed 2, aggrave mon problème et je pourrais tripler le # que je pourrais générer si je l'éliminais. En pratique, le code fonctionne assez bien. La 3125ème itération de Morris aurait plus de 10^359 caractères de longueur.

Le problème que j'essaie vraiment de résoudre est de savoir comment conserver l'eval paresseux et ne pas avoir de limite en fonction de la taille de la pile pour l'itération que je peux détecter. Je suis à la recherche de l'idiome F # approprié pour faire la limite basée sur la taille de la mémoire.

Mise à jour octobre '10

Après avoir appris F # un peu mieux, un petit peu de Haskell, en pensant & enquêter sur ce problème depuis plus d'année, je peux enfin répondre à ma propre question. Mais comme toujours avec des problèmes difficiles, le problème commence avec la mauvaise question. Le problème n'est pas des séquences de séquences - c'est vraiment à cause d'une séquence récursivement définie. Mes compétences en programmation fonctionnelle sont un peu mieux maintenant et il est donc plus facile de voir ce qui se passe avec la version ci-dessous, qui obtient encore 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)) 

Cela crée basicially une chaîne très longue de la fonction de traitement Seq appels pour générer la les suites. Le module Seq fourni avec F # est ce qui ne peut pas suivre la chaîne sans utiliser la pile. Il y a une optimisation qu'il utilise pour les séquences append et récursivement définies, mais cette optimisation ne fonctionne que si la récursion implémente un append.

donc ça marchera

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

Et celui-ci aura une stackoverflow.

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

Pour prouver le F # libary était la question, je l'ai écrit mon propre module Seq qui a mis append, par paires, de numérisation et de recueillir l'aide continutions et maintenant je peux commencer à générer et imprimer les 50 000 suivants sans problème (il ne finira jamais car il fait plus de 10^5697 chiffres).

Quelques notes supplémentaires:

• continuations étaient l'idiome que je cherchais, mais dans ce cas, ils ont dû aller dans la bibliothèque F #, mon code. J'ai appris des suites dans F # de Tomas Petricek'sReal-World Functional Programming livre.
• La réponse liste paresseuse que j'ai acceptée contenait l'autre idiome; évaluation paresseuse. Dans ma bibliothèque réécrite, j'ai également dû tirer parti du type paresseux pour éviter le stackoverflow. La version de liste paresseuse sorta des œuvres par chance (peut-être par conception mais cela dépasse ma capacité actuelle à déterminer) - la correspondance de pattern active utilisée pendant sa construction et son itération amène les listes à calculer des valeurs avant que la récursivité requise profond, donc c'est paresseux, mais pas si paresseux il a besoin de continuations pour éviter le stackoverflow. Par exemple, au moment où la 2e séquence a besoin d'un chiffre de la 1ère séquence, elle a déjà été calculée. En d'autres termes, la version LL n'est pas strictement JIT paresseux pour la génération de séquence, seulement la gestion des listes.

Answer 1

Vous devez absolument vérifier

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

mais je vais essayer de poster une réponse plus complète plus tard.

UPDATE

Ok, une solution est au-dessous. Il représente la séquence de Morris comme LazyList de LazyLists de int, puisque je suppose que vous voulez qu'il soit paresseux dans les deux sens.

Le F # LazyList (dans le FSharp.PowerPack.dll) a trois propriétés utiles:

• il est paresseux (évaluation de l'élément n-ième ne se produira pas jusqu'à ce qu'il soit d'abord exigé)
• il le fait pas recalculer (la réévaluation du nième élément sur la même instance d'objet ne le recalculera pas - il met en cache chaque élément après le premier calcul)
• vous pouvez oublier les préfixes (comme vous «queue» dans la liste, le non le préfixe -longer-référencé est disponible pour la récupération de place)

La première propriété est commune avec seq (IEnumerable), mais les deux autres sont uniques à LazyList et très utile pour les problèmes de calcul tels que celui posé dans cette question.

Sans plus tarder, le code:

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

MAJ2

Si vous voulez juste compter, qui est très bien aussi:

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()  

Le reste utilisation de la mémoire plate (sous 16M sur ma boîte) ... n'a pas encore fini de courir, mais j'ai calculé la 55ème longueur rapidement, même sur ma boîte lente, donc je pense que cela devrait fonctionner très bien. Notez aussi que j'ai utilisé 'bignum's pour la longueur, puisque je pense que cela va déborder un' int '.

Answer 2

Sauvegardez simplement l'élément précédent que vous avez recherché.

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) 
} 

Answer 3

Je crois qu'il ya deux principaux problèmes ici:

• Paresse est très inefficace, et vous pouvez vous attendre une implémentation fonctionnelle paresseux pour exécuter des ordres de grandeur plus lente. Par exemple, l'implémentation de Haskell décrite here est 2 400 × plus lente que la F # I donnée ci-dessous. Si vous voulez une solution de contournement, votre meilleur pari est probablement d'amortir les calculs en les regroupant en lots désireux où les lots sont produits sur demande. La fonction Seq.append appelle réellement le code C# de IEnumerable et, par conséquent, son appel de queue n'est pas éliminé et vous perdez un peu plus d'espace de pile chaque fois que vous le traversez. Cela apparaît lorsque vous venez énumérer la séquence.

Voici plus de 80 × plus vite que votre mise en œuvre au calcul de la longueur de la 50e séquence mais peut-être il ne suffit pas paresseux pour vous:

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]) 

Le noyau de cette fonction est un pli sur un ResizeArray qui pourrait être factorisé et utilisé de manière fonctionnelle sans trop de dégradation des performances si vous utilisiez une structure comme accumulateur.