F # usando caché secuencia correcta

Question

Estoy tratando de utilizar Seq.cache con una función que hice que devuelve una secuencia de números primos hasta un número sin incluir el número 1. Estoy teniendo problemas para encontrar la manera de mantener la secuencia en caché en su alcance, pero N todavía utilizarlo en mi definición.

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

¿Alguna idea de cómo podría utilizar Seq.cache para hacer esto más rápido? Actualmente se mantiene al pasar de alcance y sólo se está ralentizando el rendimiento.

Answer 1

Seq.cache caché una IEnumerable<T> ejemplo de manera que cada elemento de la secuencia se calcula únicamente una vez. En su caso, sin embargo, que estés almacenamiento en caché de la secuencia devuelto por una función, y cada vez que se llama a la función que conseguir un nueva secuencia de caché, que no le hace ningún bien. No creo que el almacenamiento en caché es realmente el enfoque adecuado para su problema, ya que se ha contorneado; en su lugar, probablemente debería mirar en memoization.

Si en lugar de definir una función que da los números primos menores de n que desea definir una secuencia infinita numerable de números primos, a continuación, el almacenamiento en caché tiene más sentido. Que se vería más como esto:

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

No he comparado el rendimiento de este método en comparación con la suya.

Answer 2

Me di cuenta de cómo solucionar mi problema con un doblez pero no es mi idea de utilizar 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

¿Se ha tomado un vistazo a LazyList? Parece que está diseñado para resolver el mismo problema. Está en PowerPack.