Простое число ленивая последовательность

Question

Я новичок в F # и мне просто интересно, есть ли способ получить ленивую последовательность простых чисел в F #.

В Хаскеле я использую следующий код:

primes :: [Integer]
primes = sieve[2..]
       where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]

В F # я могу проверить, является ли число простым:

let isPrime (number : bigint) =
    match number with
        | _ -> seq { bigint(2) .. bigint(Math.Sqrt(float number))}
        |> Seq.exists (fun x -> if (number % x = bigint(0)) then true else false)
        |> not

Но я не знаю, как преобразовать его в ленивую последовательность.

Answer 1

См. этот вопрос для многих ответов, дающих ленивые последовательности простых чисел в F #.

Для наивного решения, использующего вашу реализацию isPrime (т. Е. Я думаю, что вам может быть интересно узнать, как генерировать бесконечную последовательность из функции фильтра в целом), попробуйте следующее:

let primes =
    Seq.initInfinite (fun i -> i + 2) //need to skip 0 and 1 for isPrime
    |> Seq.map (fun i -> bigint(i))
    |> Seq.filter isPrime

Тем не менее, вы, вероятно, захотите решить проблему 3 проекта Эйлера по-другому, реализовав функцию, которая специально разлагает число на части, а не разбивает число на простые числа и принимает наибольшее. Хотя в дальнейшем вам понадобится генератор простых последовательностей для дальнейших задач.

Answer 2

Если вы хотите имитировать лень Хаскелла, вы можете использовать тип LazyList, найденный в FSharp.PowerPack.dll. LazyList.Cons (p, xs) - это сопоставление с шаблоном, соответствующее p: xs в Haskell. «Задержка» в consDelayed необходима, потому что обычные LazyList.cons будут слишком энергичными и будут бесконечно долго (конечно, с вашим терпением) долго.

Вы также можете найти этот вопрос интересным. Это еще одно простое сито Haskell в F #.

Вот ваш код на F # (к сожалению, довольно уродливый):

#r "FSharp.PowerPack.dll"

//A lazy stream of numbers, starting from x
let rec numsFrom x = LazyList.consDelayed x (fun () -> numsFrom (x+1I))

let rec sieve = function
    | LazyList.Cons(p,xs) ->
        LazyList.consDelayed p (fun () -> 
                xs |> LazyList.filter (fun x -> x%p <> 0I) |> sieve)
    | _ -> failwith "This can't happen with infinite lists"

let primes() = sieve (numsFrom 2I)

Пример вывода в FSI:

> primes() |> Seq.take 14 |> Seq.toList;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : System.Numerics.BigInteger list =
  [2I; 3I; 5I; 7I; 11I; 13I; 17I; 19I; 23I; 29I; 31I; 37I; 41I; 43I]

Answer 3

Мое решение без F # powerpack

module Prime
    let isPrime n = 
        let bound = int (sqrt(float n))
        seq{2..bound}
        |> Seq.exists (fun x -> n % x = 0) 
        |> not
    let rec nextPrime n = 
        if isPrime (n + 1) then n + 1
        else nextPrime (n+1)
    let sequence = 
        Seq.unfold(fun n -> Some(n, nextPrime n)) 1