F # usando correttamente la cache sequenza

Question

Sto cercando di utilizzare Seq.cache con una funzione che ho fatto che restituisce una sequenza di numeri primi fino ad un numero N escluso il numero 1. Non riesco a capire come mantenere la sequenza cache portata, ma ancora usarlo nella mia definizione.

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

Tutte le idee su come avrei potuto usare Seq.cache per rendere questo più veloce? Attualmente continua a cadere dal campo di applicazione ed è solo rallentando le prestazioni.

Answer 1

Seq.cache cache una IEnumerable<T> istanza in modo che ciascun elemento della sequenza viene calcolato una sola volta. Nel tuo caso, però, si sta caching la sequenza restituito da una funzione, e ogni volta che si chiama la funzione si ottiene un nuovo sequenza di cache, che non fa nulla di buono. Non credo che la cache è davvero il giusto approccio al problema come hai delineato esso; invece probabilmente si dovrebbe guardare in Memoizzazione.

Se invece di definire una funzione che dà i primi minori di n si desidera definire una sequenza enumerabile infinita di numeri primi, poi il caching ha più senso. Che sarebbe più simile a questo:

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

Non ho confrontato le prestazioni di questo metodo rispetto alla tua.

Answer 2

ho capito come risolvere il mio problema con una piega, ma non la mia idea di utilizzare 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

Avete dato un'occhiata a lazylist? Sembra come se fosse stato progettato per risolvere lo stesso problema. E 'in PowerPack.