F # usando secuencia de caché correctamente

Question

Estoy tratando de usar Seq.cache con una función que hice que devuelve una secuencia de números primos hasta un número N excluyendo el número 1. Tengo problemas para averiguar cómo mantener el secuencia en caché en el alcance, pero todavía lo uso 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 usar Seq.cache para hacer esto más rápido? Actualmente sigue bajando del alcance y solo está frenando el rendimiento.

Answer 1

Seq.cache almacena en caché una instancia de IEnumerable<T> de modo que cada elemento de la secuencia solo se calcule una vez. En su caso, sin embargo, está almacenando en caché la secuencia devuelta por una función, y cada vez que llama a la función obtiene una nueva secuencia en caché , que no le sirve de nada. No creo que el almacenamiento en caché sea realmente el enfoque correcto para su problema como lo ha descrito; en su lugar, probablemente deberías mirar en la memorización.

Si en lugar de definir una función que proporcione los números primos menores que n, desea definir una secuencia enumerable infinita de números primos, entonces el almacenamiento en caché tiene más sentido. Eso 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 el suyo.

Answer 2

Descubrí cómo resolver mi problema con un doblez pero no con mi idea de usar 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

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