Haskell -> f#: peneira de Turner

Question

Eu estava lendo sobre diferentes algoritmos de peneiração quando me deparei com uma espécie de versão melhorada da peneira de eratóstenes chamada Penela de Euler. De acordo com Wikipedia Há uma implementação de uma versão ligeiramente diferente da idéia (chamada Turner's Sieve) em Haskell.

Agora estou tentando entender o que exatamente o snippet de código dado e acho que tenho, mas agora queria traduzir o código em F# e realmente não tenho idéia por onde começar. Minha principal preocupação é que não pareça haver uma função para "subscrever" duas seqüências.

Aqui está o código:

import Data.OrdList (minus)

primes = euler [2..]
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs))

Como isso seria implementado em F#? Isso é possível?

Answer 1

Se você deseja calcular coisas como mesclagem/diferenças de listas infinitas como Haskell, o tipo lazylist (encontrado dentro do F# Power Pack) vem à mente.

Faz um código muito detalhado, como a tradução abaixo:

#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)

com

> 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]

Observe que eu adicionei dois failwith As cláusulas para impedir que o compilador reclamasse de uma correspondência incompleta, mesmo que saibamos que todas as listas no cálculo são (preguiçosamente) infinitas.

Answer 2

Você pode fazer isso com Seq. E como você tem menos feito, Euler O próprio é o mesmo que em 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

Answer 3

Com sequências, você fica muito mais competitivo ao persistir a sequência:

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
    }

Answer 4

Primeiro, deve -se dizer que a peneira do Euler para números primos não é uma "versão melhorada da peneira de eratóstenes", pois seu desempenho em todos os sentidos é muito pior do que qualquer versão da peneira de eratóstenos: Haskell Wiki em algoritmos de números primos - Euler

Em seguida, deve -se dizer que o código do @CFEM usando o Lazylist é um fiel, embora a tradução detalhada da versão da peneira de Euler que você deu, embora não tenha a ligeira melhoria de apenas peneirar números ímpares, conforme o link acima.

Deve -se notar que não há realmente nenhum ponto na implementação da peneira Euler, pois é mais complexa e mais lenta do que encontrar primos pela divisão de teste otimizados (TDO) para fazer apenas divisões por primos encontrados até a raiz quadrada do Número do candidato testado para o Prime conforme: Haskell Wiki em algoritmos de números primos - TDO.

este Peneira otimizada da divisão de estudo (TDO) pode ser implementado em F# usando o Lazylist (com uma referência ao fsharp.powerpack.dll) como:

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)

Ele pode ser implementado usando sequências da mesma forma que:

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 }

A versão de sequência é um pouco mais rápida que a versão lazylist, porque evita algumas despesas gerais em chamadas, já que o Lazylist é baseado em sequências em cache. Ambos usam um objeto interno que representa uma cópia em cache dos primos encontrados até agora, automaticamente em cache no caso de Lazylist e pelo seq.cache no caso de seqüências. Ou pode encontrar os primeiros 100.000 primos em cerca de dois segundos.

Agora o Peneira Euler pode ter a otimização de peneiração de números ímpares e ser expressa usando o Lazylist como o seguinte, com um caso de partida eliminado devido a saber que os parâmetros da lista de entrada são infinitos e a correspondência de comparação simplificada, bem como eu adicionei um operador '^' para fazer O código mais legível:

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))

No entanto, deve -se notar que o tempo para calcular o 1899º Prime (16381) é de cerca de 0,2 e 0,16 segundos para o Primestdo e Primestdos, respectivamente, enquanto há cerca de 2,5 segundos usando esse primese para um desempenho terrível para a peneira de Euler a mais Dez vezes o tempo, mesmo para esse pequeno alcance. Além do desempenho terrível, o Primee não pode nem calcular os primos a 3000 devido à utilização de memória ainda pior, pois registra um número crescente de funções de execução diferidas com o aumento dos primos encontrados.

Observe que é preciso ter cuidado no tempo repetido do código, como escrito, pois o lazylist é um valor e possui memorização interna de elementos encontrados anteriormente; portanto, uma segunda varredura idêntica levará quase zero tempo; Para fins de tempo, pode ser melhor tornar o Primee uma função como no primeiro (), para que o trabalho comece a partir do início a cada vez.

Em resumo, a peneira Euler implementada em qualquer idioma, incluindo F#, é apenas um exercício intelectual interessante e não tem uso prático, pois é muito mais lento e a memória de Hogs é muito pior do que quase todas as outras peneiras razoavelmente otimizadas.