Haskell --› F#: сито Тернера

Если вы хотите вычислять такие вещи, как слияния/разности бесконечных списков, как это делает Haskell, на ум приходит тип LazyList (находящийся в пакете питания F#).

Это делает код очень подробным, как в приведенном ниже переводе:

#r "FSharp.PowerPack.dll"

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

//subtracts L2 from L1, where L1 and L2 are both sorted(!) lazy lists
let rec lazyDiff L1 L2 =
    match L1,L2 with
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1<x2 ->
            LazyList.consDelayed x1 (fun () -> lazyDiff xs1 L2)
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1=x2 ->
            lazyDiff xs1 L2
        | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1>x2 ->
            lazyDiff L1 xs2
        | _ -> failwith "Should not occur with infinite lists!"

let rec euler = function
    | LazyList.Cons(p,xs) as LL ->
        let remaining = lazyDiff xs (LazyList.map ((*) p) LL)
        LazyList.consDelayed p (fun () -> euler remaining)
    | _ -> failwith "Should be unpossible with infinite lists!"

let primes = euler (numsFrom 2)

с участием

> primes |> Seq.take 15 |> Seq.toList;;
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]

Обратите внимание, что я добавил два предложения failwith, чтобы компилятор не жаловался на неполное совпадение, даже если мы знаем, что все списки в вычислении (лениво) бесконечны.

Вы можете сделать это с помощью seq. И поскольку вы сделали minus, euler сам по себе такой же, как в Haskell.

let rec minus xs ys =
  seq {
    match Seq.isEmpty xs, Seq.isEmpty ys with
    | true,_ | _,true -> yield! xs
    | _ ->
       let x,y = Seq.head xs, Seq.head ys
       let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys
       match compare x y with
       | 0 -> yield! minus xs' ys'
       | 1 -> yield! minus xs ys'
       | _ -> yield x; yield! minus xs' ys
  }

let rec euler s =
  seq {
    let p = Seq.head s
    yield p
    yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
  }

let primes = Seq.initInfinite ((+) 2) |> euler

С последовательностями вы становитесь намного более конкурентоспособным, сохраняя последовательность:

let rec euler s =
    seq {
        let s = Seq.cache s
        let p = Seq.head s
        yield p
        yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler
    }

Во-первых, необходимо сказать, что решето Эйлера для простых чисел не является «улучшенной версией решета Эратосфена», поскольку его производительность во всех смыслах намного хуже любой версии решета Эратосфена: Haskell Wiki по алгоритмам простых чисел — Эйлер

Далее следует сказать, что код @cfem, использующий LazyList, является точным, хотя и многословным переводом версии решета Эйлера, которую вы дали, хотя ему не хватает небольшого улучшения просеивания только нечетных чисел по ссылке выше.

Следует отметить, что на самом деле нет никакого смысла в реализации решета Эйлера, так как это сложнее и медленнее, чем поиск простых чисел с помощью оптимизации пробного деления (TDO), поскольку деление выполняется только на найденные простые числа до квадратного корня из число-кандидат проверено на простое число согласно: Haskell Wiki по алгоритмам простых чисел — TDO.

Это сито Trial Division Optimized (TDO) может быть реализовано на F# с использованием LazyList (со ссылкой на FSharp.PowerPack.dll) следующим образом:

let primesTDO() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then LazyList.consDelayed n (fun() -> oddprimesFrom (n + 2))
      else oddprimesFrom (n + 2)
    LazyList.consDelayed 3 (fun() -> oddprimesFrom 5)
  LazyList.consDelayed 2 (fun () -> oddprimes)

Это может быть реализовано с использованием последовательностей в той же форме, что и:

let primesTDOS() =
  let rec oddprimes =
    let rec oddprimesFrom n =
      if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0)
      then seq { yield n; yield! oddprimesFrom (n + 2) }
      else oddprimesFrom (n + 2)
    seq { yield 3; yield! (oddprimesFrom 5) } |> Seq.cache
  seq { yield 2; yield! oddprimes }

Версия последовательности немного быстрее, чем версия LazyList, потому что она позволяет избежать некоторых накладных расходов при вызове, поскольку LazyList основан на кэшированных последовательностях. Оба используют внутренний объект, который представляет кэшированную копию простых чисел, найденных до сих пор, автоматически кэшируемых в случае LazyList и Seq.cache в случае последовательностей. Любой может найти первые 100 000 простых чисел примерно за две секунды.

Теперь решето Эйлера может иметь оптимизацию просеивания нечетных чисел и быть выражено с помощью LazyList следующим образом, с исключением одного случая совпадения из-за того, что параметры входного списка бесконечны, а сопоставление упрощено, как ну, я добавил оператор '^', чтобы сделать код более читабельным:

let primesE = //uses LazyList's from referenced FSharp.PowerPack.dll version 4.0.0.1
  let inline (^) a ll = LazyList.cons a (LazyList.delayed ll) //a consd function for readability
  let rec eulers xs =
    //subtracts ys from xs, where xs and ys are both sorted(!) infinite lazy lists
    let rec (-) xs ys =
      let x,xs',ys' = LazyList.head xs,LazyList.tail xs,LazyList.tail ys
      match compare x ( LazyList.head ys) with
        | 0 -> xs' - ys' // x == y
        | 1 -> xs - ys' // x > y
        | _ -> x^(fun()->(xs' - ys)) // must be x < y
    let p = LazyList.head xs
    p^(fun() -> (((LazyList.tail xs) - (LazyList.map ((*) p) xs)) |> eulers))
  let rec everyothernumFrom x = x^(fun() -> (everyothernumFrom (x + 2)))
  2^(fun() -> ((everyothernumFrom 3) |> eulers))

Однако следует отметить, что время вычисления 1899-го простого числа (16381) составляет около 0,2 и 0,16 секунды для простых чисел TDO и PrimesTDOS соответственно, в то время как при использовании этого простого числа E для ужасной производительности решета Эйлера при более чем 2,5 секунды в десять раз больше времени даже для этого небольшого диапазона. В дополнение к ужасной производительности, PrimeE не может даже вычислить простые числа до 3000 из-за еще большего использования памяти, поскольку он записывает быстро растущее количество отложенных функций выполнения с увеличением найденных простых чисел.

Обратите внимание, что нужно быть осторожным при повторении времени написания кода, поскольку LazyList является значением и имеет встроенное запоминание ранее найденных элементов, поэтому второе идентичное сканирование займет почти нулевое время; для целей синхронизации может быть лучше сделать PrimeE функцией, как в PrimeE(), чтобы работа каждый раз начиналась с самого начала.

Таким образом, решето Эйлера, реализованное на любом языке, включая F#, является всего лишь интересным интеллектуальным упражнением и не имеет практического применения, поскольку оно намного медленнее и потребляет гораздо больше памяти, чем почти любое другое разумно оптимизированное решето.