F # usando cache de seqüência corretamente

Question

Eu estou tentando usar Seq.cache com uma função que eu fiz que retorna uma seqüência de números primos até um número N excluindo o número 1. Estou tendo dificuldade para descobrir como manter a seqüência em cache no escopo, mas ainda usá-lo na minha definição.

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

Todas as idéias de como eu poderia usar Seq.cache para fazer isso mais rápido? Atualmente ele mantém caindo de escopo e só está a abrandar o desempenho.

Answer 1

Seq.cache armazena uma instância IEnumerable<T> de modo que cada artigo na sequência é calculada apenas uma vez. No seu caso, porém, você está cache a seqüência retornada por uma função, e cada vez que você chamar a função que você obter um nova sequência em cache, o que não fará nenhum bom. Eu não acho que o cache é realmente a abordagem certa para o seu problema como você esbocei-lo; em vez disso você provavelmente deve olhar para memoization.

Se em vez de definir uma função dando os números primos menos de n você deseja definir uma seqüência enumerável infinito de primos, então cache faz mais sentido. Isso seria mais parecido com isto:

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

Eu não comparou o desempenho deste método em comparação com o seu.

Answer 2

Eu descobri como resolver o meu problema com uma dobra, mas não a minha ideia 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

Você deu uma olhada em LazyList? Parece que é projetado para resolver o mesmo problema. É no PowerPack.