12

昨日、空き時間に F# を調べ始めました。100 までのすべての素数を出力するという標準的な問題から始めようと思いました。

#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

問題は、C/C# の観点からこれにアプローチしたように感じ、真の関数型言語の側面を受け入れていないことです。

他の人が何を思い付くことができるのか、そして誰かがヒント/ポインター/提案​​を持っているかどうか疑問に思っていました. F# のコンテンツは現在 Web で入手するのが難しく、私が最後に触れた関数型言語は大学時代の 5 年前にHOPEでした。

4

7 に答える 7

9

F#でのエラトステネスのふるいの簡単な実装を次に示します。

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]

この実装は非常に大きなリストでは機能しませんが、機能的なソリューションの優雅さを示しています。

于 2009-07-08T11:52:17.453 に答える
3

Eratosthenesのような Sieve 関数を使用するのが良い方法です。関数型言語はリストで非常にうまく機能するので、構造についてはそれを念頭に置いて始めます。

別の注意点として、関数型言語は関数からうまく構築されて機能します (へー)。関数型言語の「感じ」については、Sieve 関数を作成し、それを呼び出して素数を出力します。分割することもできます。1 つの関数がリストを作成してすべての作業を行い、もう 1 つの関数がすべての印刷を実行して、機能をきちんと分離します。

ここには興味深いバージョンがいくつかあります。また、他の同様の言語にもよく知られている実装があります。 これは、C の 1 つに勝る OCAMLの 1つです。

于 2009-07-08T11:36:00.950 に答える
3

ここに私の2セントがあります：

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

isprimeまたは、別の関数として定義されているのと同じものの、このより明確なバージョンかもしれません:

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
    }
于 2016-03-13T04:00:15.767 に答える
2

この例から学びたいとは思わないでしょうが、私はメッセージ パッシングに基づくNewSqueak ふるいの F# 実装を作成しました。

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

それは機能しますか？

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

甘い！:)

于 2009-07-08T15:20:45.093 に答える
1

これは、HubFSでの、再帰的なseqを使用して素数ジェネレーターを実装することについての私の古い投稿です。

迅速な実装が必要な場合は、MarkusMottlによる素晴らしいOCamlコードがあります。

PS 10 ^ 20までの素数を繰り返したい場合は、DJ Bernsteinによる素数をF＃/OCamlに移植したいです:)

于 2009-07-21T16:20:41.990 に答える
1

シンプルだが非効率的な提案:

  • 単一の数値が素数かどうかをテストする関数を作成する
  • 2 から 100 までの数字のリストを作成する
  • 関数でリストをフィルタリングする
  • 結果を別の関数で構成して結果を出力する

これを効率的にするには、メモ化が必要な、より低い素数で割り切れるかどうかをチェックすることで、素数であるかどうかをテストする必要があります。おそらく、最初に単純なバージョンが機能するまで待つのが最善です:)

それがヒントとして十分でない場合は教えてください。完全な例を考え出します - 今夜までではないかもしれないと思っていました...

于 2009-07-08T11:17:14.387 に答える
1

同じ問題を解決しながら、F#で Atkins のふるいを実装しました。これは、最も効率的な最新のアルゴリズムの 1 つです。

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

Parallel Async の使用を推奨しない人もいることは知っていますが、私の 2 コア (ハイパースレッディングでは 4) i5 で速度が最大 20% 向上しました。これは、TPL を使用して得たのとほぼ同じ増加です。

機能的な方法で書き直して、ループと変更可能な変数を読み取ろうとしましたが、パフォーマンスが 3 ～ 4 回低下したため、このバージョンを保持することにしました。

于 2015-10-27T16:30:43.173 に答える