F # unter Verwendung von Sequenz Cache korrekt

Question

Ich versuche Seq.cache mit einer Funktion zu verwenden, die ich gemacht, die eine Folge der Primzahlen bis zu einer Zahl N gibt mit Ausnahme der Nummer 1. Ich habe Probleme, herauszufinden, wie die Cache-Sequenz in Rahmen zu halten, aber verwenden sie es immer noch in meiner Definition.

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

Irgendwelche Ideen, wie ich Seq.cache verwenden könnte dies schneller zu machen? Derzeit hält sie vom Anwendungsbereich fallen und wird nur die Leistung verlangsamt.

Answer 1

Seq.cache Caches eine IEnumerable<T> Instanz, so dass jedes Element in der Sequenz nur einmal berechnet wird. In Ihrem Fall, obwohl, sind Cachen Sie die Reihenfolge von einer Funktion zurück, und jedes Mal, wenn Sie die Funktion aufrufen, erhalten Sie eine neue im Cache-Sequenz, die dir nicht gut tut. Ich glaube nicht, Caching ist wirklich der richtige Ansatz, um das Problem, wie Sie es skizziert habe; stattdessen sollten Sie vielleicht in memoization aussehen.

Wenn stattdessen eine Funktion der Definition der Primzahlen kleiner als n geben Sie eine unendliche zählbare Folge von Primzahlen definieren wollen, dann macht Caching mehr Sinn. Das wäre mehr wie folgt aussehen:

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

Ich habe die Durchführung dieses Verfahrens nicht im Vergleich im Vergleich zu Ihnen.

Answer 2

ich herausgefunden, wie mein Problem mit einer Falte, aber nicht meine Idee zu lösen seq.cache zu verwenden.

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

Haben Sie einen Blick auf LazyList genommen? Scheint, wie es das gleiche Problem zu lösen, wird entwickelt. Es ist in Power Pack.