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.