Избегайте (с бесконечными последовательностями последовательностей F #)

У меня есть этот "учебный код", который я написал для morris seq в f #, который страдает от, который я не знаю, как этого избежать. "morris" возвращает бесконечную последовательность последовательностей "видеть и говорить" (т.е. {{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  // Qaru 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 

Вы можете выбрать n-ю итерацию с помощью Seq.nth, но вы можете получить только до того, как попадете в переполнение стека. Один бит рекурсии у меня есть хвостовая рекурсия, и она по сути строит связанный набор счетчиков. Это не там, где проблема. Это когда "enum" вызывается, скажем, 4000-й последовательностью. Обратите внимание, что с F # 1.9.6.16 предыдущая версия превысила 14 000). Это связано с тем, что связанные между собой последовательности разрешены. Последовательности являются ленивыми, и поэтому "рекурсия" ленива. То есть seq n вызывает seq n-1, который вызывает seq n-2 и т.д., Чтобы получить первый элемент (самый первый из них - худший случай).

Я понимаю, что [|0|] |> Seq.append str |> Seq.windowed 2, делает мою проблему хуже, и я мог бы утроить #, которую я мог бы сгенерировать, если бы я ее устранил. Практически говоря, код работает достаточно хорошо. 3125-я итерация морриса будет длиной более 10 359 символов.

Проблема, которую я действительно пытаюсь решить, заключается в том, как сохранить ленивый eval и не иметь ограничений, основанных на размере стека для итерации, которую я могу выбрать. Я ищу подходящую идиому F #, чтобы сделать ограничение на основе размера памяти.

Обновить октябрь '10

Узнав F # немного лучше, крошечный бит Хаскелла, размышляя и исследуя эту проблему в течение года, я, наконец, могу ответить на свой вопрос. Но, как всегда, с трудными проблемами, проблема начинается с того, что это неправильный вопрос. Проблема состоит не в последовательности последовательностей - это действительно из-за рекурсивно определенной последовательности. Мои навыки функционального программирования сейчас немного лучше, и поэтому легче увидеть, что происходит с приведенной ниже версией, которая по-прежнему получает 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))

Это фундаментально создает действительно длинную цепочку вызовов обработки Seq для генерации sequnces. Модуль Seq, который поставляется с F #, не может следовать цепочке, не используя стек. Там оптимизация используется для добавления и рекурсивно определенных последовательностей, но эта оптимизация работает только в том случае, если рекурсия реализует добавление.

Итак, это будет работать

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

И этот получит пакетный поток.

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

Чтобы доказать, что проблема F # libary была проблемой, я написал свой собственный модуль Seq, который реализовал добавление, попадание, сканирование и сбор с использованием контуров, и теперь я могу начать генерировать и распечатывать 50 000 секунд без проблем (он никогда не закончится так как он длиннее 10 ^ 5697 цифр).

Некоторые дополнительные примечания:

• Продолжения были идиомой, которую я искал, но в этом случае они должны были войти в библиотеку F #, а не мой код. Я узнал о продолжениях в F # из "Книга функционального программирования в реальном мире" Томаса Петричека.
• Ответ на ленивый список, который я принял, придерживался другой идиомы; ленивая оценка. В моей переписанной библиотеке мне также пришлось использовать ленивый тип, чтобы избежать stackoverflow.
• Версия ленивого списка сортирует работы по удаче (может быть, по дизайну, но за пределами моей текущей способности определять) - сопоставление активного шаблона, используемое при его построении и итерации, заставляет списки вычислять значения до того, как требуется рекурсия глубокий, поэтому он ленив, но не так ленив, ему нужны продолжения, чтобы избежать stackoverflow. Например, к моменту, когда вторая последовательность нуждается в цифре из первой последовательности, она уже была рассчитана. Другими словами, версия LL не является строго JIT ленивой для генерации последовательности, только управление списками.

Ответы

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

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

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

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