F # en utilisant correctement le cache de séquence

Question

Je suis en train d'utiliser Seq.cache avec une fonction que je fait qui retourne une séquence de nombres premiers jusqu'à un nombre N hors le numéro 1. Je vais avoir du mal à comprendre comment garder la séquence en cache portée mais utiliser encore dans ma définition.

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

Toutes les idées de la façon dont je pourrais utiliser Seq.cache pour faire de ce plus rapide? Actuellement, il continue de laisser tomber la portée et ne ralentit les performances.

Answer 1

Seq.cache en mémoire cache une IEnumerable<T> exemple de telle sorte que chaque élément de la séquence est calculé seulement une fois. Dans votre cas, cependant, vous cache la séquence renvoyée par une fonction, et chaque fois que vous appelez la fonction que vous obtenez une nouveau séquence en cache, ce qui ne fera aucun bien. Je ne pense pas que la mise en cache est vraiment la bonne approche à votre problème que vous avez décrit cela; au contraire, vous devriez probablement dans memoization.

Si au lieu de définir une fonction donnant les nombres premiers inférieurs que vous souhaitez n définir une séquence dénombrable infinie de nombres premiers, puis la mise en cache est plus logique. Cela ressemble davantage à ceci:

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

Je ne l'ai pas comparé la performance de cette méthode par rapport à la vôtre.

Answer 2

Je me suis dit comment résoudre mon problème avec un pli, mais pas mon idée d'utiliser 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

Avez-vous pris un coup d'œil à LazyList? On dirait qu'il est conçu pour résoudre le même problème. Il est en PowerPack.