Aprendiendo F # - imprimiendo números primos

Question

Ayer comencé a mirar F # durante algún tiempo libre. Pensé que iba a comenzar con el problema de calidad de impresión de todos los números primos hasta 100. Esto es lo que se me ocurrió ...

#light 
open System 

let mutable divisable = false 
let mutable j = 2 

for i = 2 to 100 do 
    j <- 2 
    while j < i do 
     if i % j = 0 then divisable <- true 
     j <- j + 1 

    if divisable = false then Console.WriteLine(i) 
    divisable <- false 

La cosa es que me siento como que se han acercado a esto desde un C/C# perspectiva y no abrazó el verdadero aspecto del lenguaje funcional.

Me preguntaba qué podrían hacer otras personas, y si alguien tiene algún consejo/sugerencia. Siento que el contenido de F # es difícil de encontrar en la web en este momento, y el último lenguaje funcional que toqué fue HOPE hace unos 5 años en la universidad.

Answer 1

simple pero ineficiente sugerencia:

• crear una función para probar si un solo número es primo
• Crear una lista de números de 2 a 100
• Filtrar la lista por la función
• Componer el resultado con otra función para imprimir los resultados

Para que esto sea eficiente, realmente y para probar que un número sea primo al verificar si es divisible por primos inferiores o no, lo que requerirá memorización. Probablemente sea mejor esperar hasta que tenga la versión simple funcionando primero :)

Avíseme si no es suficiente una pista y le daré un ejemplo completo - pensé que podría no ser hasta esta noche ...

Answer 2

Usar una función Sieve como Eratosthenes es una buena forma de hacerlo. Los lenguajes funcionales funcionan muy bien con listas, así que comenzaría con eso en mente para struture.

En otra nota, los lenguajes funcionales funcionan bien construidos a partir de funciones (heh). Para una "sensación" de lenguaje funcional, construiría una función Sieve y luego la llamaría para imprimir los números primos. Incluso podría dividirlo: una función crea la lista y hace todo el trabajo, y se realiza una impresión, separando claramente la funcionalidad.

Hay un par de versiones interesantes here. Y hay implementaciones bien conocidas en otros idiomas similares. Here's one en ocaml que late una en C.

Answer 3

Aquí es una implementación sencilla de la Sieve of Eratosthenes en Fa #:

let rec sieve = function 
    | (p::xs) -> p :: sieve [ for x in xs do if x % p > 0 then yield x ] 
    | []  -> [] 

let primes = sieve [2..50] 
printfn "%A" primes // [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47] 

Esta aplicación no funcionará para listas muy grandes pero ilustra la elegancia de una solución funcional .

Answer 4

que definitivamente no quieren aprender de este ejemplo, pero me escribió un F # aplicación de a NewSqueak sieve basado en paso de mensajes:

type 'a seqMsg = 
    | Die 
    | Next of AsyncReplyChannel<'a> 

type primes() = 
    let counter(init) = 
     MailboxProcessor.Start(fun inbox -> 
      let rec loop n = 
       async { let! msg = inbox.Receive() 
         match msg with 
         | Die -> return() 
         | Next(reply) -> 
          reply.Reply(n) 
          return! loop(n + 1) } 
      loop init) 

    let filter(c : MailboxProcessor<'a seqMsg>, pred) = 
     MailboxProcessor.Start(fun inbox -> 
      let rec loop() = 
       async { 
        let! msg = inbox.Receive() 
        match msg with 
        | Die -> 
         c.Post(Die) 
         return() 
        | Next(reply) -> 
         let rec filter' n = 
          if pred n then async { return n } 
          else 
           async {let! m = c.AsyncPostAndReply(Next) 
             return! filter' m } 
         let! testItem = c.AsyncPostAndReply(Next) 
         let! filteredItem = filter' testItem 
         reply.Reply(filteredItem) 
         return! loop() 
       } 
      loop() 
     ) 

    let processor = MailboxProcessor.Start(fun inbox -> 
     let rec loop (oldFilter : MailboxProcessor<int seqMsg>) prime = 
      async { 
       let! msg = inbox.Receive() 
       match msg with 
       | Die -> 
        oldFilter.Post(Die) 
        return() 
       | Next(reply) -> 
        reply.Reply(prime) 
        let newFilter = filter(oldFilter, (fun x -> x % prime <> 0)) 
        let! newPrime = oldFilter.AsyncPostAndReply(Next) 
        return! loop newFilter newPrime 
      } 
     loop (counter(3)) 2) 

    member this.Next() = processor.PostAndReply((fun reply -> Next(reply)), timeout = 2000) 

    interface System.IDisposable with 
     member this.Dispose() = processor.Post(Die) 

    static member upto max = 
     [ use p = new primes() 
      let lastPrime = ref (p.Next()) 
      while !lastPrime <= max do 
      yield !lastPrime 
      lastPrime := p.Next() ] 

Cómo funciona?

> let p = new primes();; 

val p : primes 

> p.Next();; 
val it : int = 2 
> p.Next();; 
val it : int = 3 
> p.Next();; 
val it : int = 5 
> p.Next();; 
val it : int = 7 
> p.Next();; 
val it : int = 11 
> p.Next();; 
val it : int = 13 
> p.Next();; 
val it : int = 17 
> primes.upto 100;; 
val it : int list 
= [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 
    73; 79; 83; 89; 97] 

Sweet!:)

Answer 5

Aquí es my old post at HubFS sobre el uso de las SEC recursivas para implementar generador de número primo.

Para el caso de que desee una rápida implementación, hay nice OCaml code by Markus Mottl

P. S. si desea iterar el número primo hasta 10^20 realmente desea portar primigenio por D. J. Bernstein a F #/OCaml :)

Answer 6

Al resolver el mismo problema, he implementado Sieve of Atkins en F #. Es uno de los algoritmos modernos más eficientes.

// Create sieve 
let initSieve topCandidate = 
    let result = Array.zeroCreate<bool> (topCandidate + 1) 
    Array.set result 2 true 
    Array.set result 3 true 
    Array.set result 5 true 
    result 
// Remove squares of primes 
let removeSquares sieve topCandidate = 
    let squares = 
     seq { 7 .. topCandidate} 
      |> Seq.filter (fun n -> Array.get sieve n) 
      |> Seq.map (fun n -> n * n) 
      |> Seq.takeWhile (fun n -> n <= topCandidate) 
    for n2 in squares do 
     n2 
      |> Seq.unfold (fun state -> Some(state, state + n2)) 
      |> Seq.takeWhile (fun x -> x <= topCandidate) 
      |> Seq.iter (fun x -> Array.set sieve x false) 
    sieve 

// Pick the primes and return as an Array 
let pickPrimes sieve = 
    sieve 
     |> Array.mapi (fun i t -> if t then Some i else None) 
     |> Array.choose (fun t -> t) 
// Flip solutions of the first equation 
let doFirst sieve topCandidate = 
    let set1 = Set.ofList [1; 13; 17; 29; 37; 41; 49; 53] 
    let mutable x = 1 
    let mutable y = 1 
    let mutable go = true 
    let mutable x2 = 4 * x * x 
    while go do 
     let n = x2 + y*y 
     if n <= topCandidate then 
      if Set.contains (n % 60) set1 then 
       Array.get sieve n |> not |> Array.set sieve n 

      y <- y + 2 
     else 
      y <- 1 
      x <- x + 1 
      x2 <- 4 * x * x 
      if topCandidate < x2 + 1 then 
       go <- false 
// Flip solutions of the second equation 
let doSecond sieve topCandidate = 
    let set2 = Set.ofList [7; 19; 31; 43] 
    let mutable x = 1 
    let mutable y = 2 
    let mutable go = true 
    let mutable x2 = 3 * x * x 
    while go do 
     let n = x2 + y*y 
     if n <= topCandidate then 
      if Set.contains (n % 60) set2 then 
       Array.get sieve n |> not |> Array.set sieve n 

      y <- y + 2 
     else 
      y <- 2 
      x <- x + 2 
      x2 <- 3 * x * x 
      if topCandidate < x2 + 4 then 
       go <- false 
// Flip solutions of the third equation 
let doThird sieve topCandidate = 
    let set3 = Set.ofList [11; 23; 47; 59] 
    let mutable x = 2 
    let mutable y = x - 1 
    let mutable go = true 
    let mutable x2 = 3 * x * x 
    while go do 
     let n = x2 - y*y 
     if n <= topCandidate && 0 < y then 
      if Set.contains (n % 60) set3 then 
       Array.get sieve n |> not |> Array.set sieve n 

      y <- y - 2 
     else 
      x <- x + 1 
      y <- x - 1 
      x2 <- 3 * x * x 
      if topCandidate < x2 - y*y then 
       go <- false 

// Sieve of Atkin 
let ListAtkin (topCandidate : int) = 
    let sieve = initSieve topCandidate 

    [async { doFirst sieve topCandidate } 
    async { doSecond sieve topCandidate } 
    async { doThird sieve topCandidate }] 
     |> Async.Parallel 
     |> Async.RunSynchronously 
     |> ignore 

    removeSquares sieve topCandidate |> pickPrimes 

sé que algunos no recomiendan el uso asíncrono paralelo, pero sí aumentó la velocidad de ~ 20% en mi 2 núcleo (4 con hyperthreading) i5. Que es aproximadamente el mismo aumento que obtuve usando TPL.

He intentado volver a escribir en forma funcional, siendo leídos de bucles y variables mutables, pero el rendimiento sea menor de 3-4 veces, por lo que decidió mantener esta versión.

Answer 7

Aquí están mis dos centavos:

let rec primes = 
    seq { 
    yield 2 
    yield! (Seq.unfold (fun i -> Some(i, i + 2)) 3) 
      |> Seq.filter (fun p -> 
       primes 
       |> Seq.takeWhile (fun i -> i * i <= p) 
       |> Seq.forall (fun i -> p % i <> 0)) 
    } 
    for i in primes do 
    printf "%d " i 

O tal vez esta versión más clara de lo mismo que isprime se define como una función separada:

let rec isprime x = 
    primes 
    |> Seq.takeWhile (fun i -> i*i <= x) 
    |> Seq.forall (fun i -> x%i <> 0) 

and primes = 
    seq { 
     yield 2 
     yield! (Seq.unfold (fun i -> Some(i,i+2)) 3) 
       |> Seq.filter isprime 
    }