У меня есть этот «обучающий код», который я написал для последовательности Морриса в 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 // 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
Вы можете выбрать n-ю итерацию, используя Seq.nth, но вы можете продвинуться далеко до того, как достигнете переполнения стека. Единственная рекурсия, которую я имею, - это хвостовая рекурсия, которая, по сути, создает связанный набор перечислителей. Проблема не в этом. Это когда enum вызывается, скажем, 4000-й последовательности. Обратите внимание, что с F # 1.9.6.16, предыдущая версия превысила 14000). Это потому, что разрешены связанные последовательности. Последовательности ленивы, и поэтому «рекурсия» ленива. То есть seq n вызывает seq n-1, который вызывает seq n-2 и т. Д., Чтобы получить первый элемент (самый первый # - наихудший случай).
Я понимаю, что [|0|] |> Seq.append str |> Seq.windowed 2 усугубляет мою проблему, и я мог бы утроить число #, которое я мог бы сгенерировать, если бы устранял это. Практически говоря, код работает достаточно хорошо. 3125-я итерация Морриса будет иметь длину более 10 ^ 359 символов.
Проблема, которую я действительно пытаюсь решить, состоит в том, как сохранить ленивый eval и не иметь ограничений на размер стека для итерации, которую я могу выбрать. Я ищу правильную идиому F #, чтобы сделать ограничение на основе объема памяти.
Обновление за октябрь '10
После изучения F # чуть-чуть чуть-чуть Хаскелла, размышляющего и исследующего эту проблему в течение года, я наконец-то смог ответить на свой вопрос. Но как всегда с трудными проблемами, проблема начинается с того, что это неправильный вопрос. Проблема не в последовательностях последовательностей - это действительно из-за рекурсивно определенной последовательности. Мои навыки функционального программирования теперь немного лучше, и поэтому легче увидеть, что происходит с версией ниже, которая все еще получает стекопоток
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 для генерации секвенций. Модуль 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 # была проблемой, я написал свой собственный модуль Seq, который реализовал добавление, попарно, сканирование и сборку, используя продолжения, и теперь я могу начать генерировать и распечатывать 50 000 seq без проблем (это никогда не закончится так как его длина превышает 10 ^ 5697 цифр).
Некоторые дополнительные примечания:
- Продолжения были той формой, которую я искал, но в этом случае они должны были войти в библиотеку F #, а не в мой код. О продолжениях в F # я узнал из книги Томаса Петрича Реальное функциональное программирование .
- Ответ ленивого списка, который я принял, содержал другую идиому; ленивая оценка. В моей переписанной библиотеке мне также пришлось использовать ленивый тип, чтобы избежать переполнения стека.
- Сортировка ленивых версий списка работ по счастливой случайности (может быть, по замыслу, но это не в моей нынешней способности определить) - сопоставление с активным шаблоном, которое оно использует при построении и итерации, заставляет списки вычислять значения до того, как требуемая рекурсия становится слишком глубокий, поэтому он ленивый, но не такой ленивый, ему нужны продолжения, чтобы избежать переполнения стека. Например, к тому моменту, когда 2-й последовательности требуется цифра из 1-й последовательности, она уже рассчитана. Другими словами, LL-версия не является строго JIT-ленивой для генерации последовательности, только управление списками.