Edit Question - KnowledgeHub

Title Body

I have this "learning code" I wrote for the morris seq in f# that suffers from stack overflow that I don't know how to avoid. "morris" returns an infinite sequence of "see and say" sequences (i.e., {{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 You can pick off the nth iteration using Seq.nth but you can only get so far before you hit a stack overflow. The one bit of recursion I have is tail recursion and it in essence builds a linked set of enumerators. That's not where the problem is. It's when "enum" is called on the say the 4000th sequence. Note that's with F# 1.9.6.16, the previous version topped out above 14000). It's because the way the linked sequences are resolved. The sequences are lazy and so the "recursion" is lazy. That is, seq n calls seq n-1 which calls seq n-2 and so forth to get the first item (the very first # is the worst case). I understand that [|0|] |> Seq.append str |> Seq.windowed 2 , is making my problem worse and I could triple the # I could generate if I eliminated that. Practically speaking the code works well enough. The 3125th iteration of morris would be over 10^359 characters in length. The problem I'm really trying to solve is how to retain the lazy eval and have a no limit base

Tags (comma-separated) Cancel