F # правильно использовать кеш последовательности

Question

Я пытаюсь использовать Seq.cache с функцией, которую я создал, которая возвращает последовательность простых чисел до числа N, исключая номер 1. У меня возникли проблемы с выяснением того, как сохранить кешированной последовательности в области видимости, но по-прежнему использовать ее в моем определении.

let rec primesNot1 n = 
    {2 .. n} 
    |> Seq.filter (fun i -> 
     (primesNot1 (i/2) |> Seq.for_all (fun o -> i % o <> 0))) 
    |> Seq.append {2 .. 2} 
    |> Seq.cache 

Любые идеи о том, как я могу использовать Seq.cache, чтобы сделать это быстрее? В настоящее время он продолжает снижаться из объема и лишь замедляет производительность.

Answer 1

Seq.cache кэширует экземпляр IEnumerable<T>, так что каждый элемент в последовательности вычисляется только один раз. В вашем случае, тем не менее, вы кэшируете последовательность, возвращаемую функцией, и каждый раз, когда вы вызываете эту функцию, вы получаете новую кешированную последовательность, которая не делает вам ничего хорошего. Я не думаю, что кэширование - это действительно правильный подход к вашей проблеме, как вы ее изложили; вместо этого вы должны, вероятно, заглянуть в воспоминания.

Если вместо определения функции, дающей простые числа меньше n, вы хотите определить бесконечную перечислимую последовательность простых чисел, то кеширование имеет больше смысла. Это выглядело бы так:

let rec upFrom i = 
    seq { 
    yield i 
    yield! upFrom (i+1) 
    } 

let rec primes = 
    seq { 
    yield 2 
    yield! 
     upFrom 3 |> 
     Seq.filter (fun p -> primes |> Seq.takeWhile (fun j -> j*j <= p) |> Seq.forall (fun j -> p % j <> 0)) 
    } 
    |> Seq.cache 

Я не сравнивал эффективность этого метода по сравнению с вашим.

Answer 2

Я выяснил, как решить мою проблему с помощью складки, но не использовать идею seq.cache.

let primesNot1 n = 
    {2 .. n} 
    |> Seq.fold (fun primes i -> 
     if primes |> Seq.for_all (fun o -> i % o <> 0) then 
      List.append primes [i] 
     else 
      primes) [2] 

Answer 3

Вы ознакомились с LazyList? Похоже, он разработан для решения одной и той же проблемы. Это в PowerPack.