昨天我利用一些空闲时间开始了解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# 内容很少，我最后接触的函数式语言是大约5年前在大学里接触的 HOPE。
这里是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]
p）的倍数。因此，这是当前质数的倍数步骤数。然而，您的代码对所有剩余数字进行可除性测试，而不仅仅是倍数。随着数字变得越来越大，非倍数比倍数多得多，因此与真正的筛法相比，您的算法需要做很多额外的工作。 - Jules以下是我的意见：
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
}
你肯定不想从这个例子中学习，但我编写了一个基于消息传递的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]
在解决同样的问题时，我已经使用F#实现了Atkins筛法。这是最有效的现代算法之一。
// 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，但在我的双核（超线程4核）i5上，它的速度提高了约20％。这与我使用TPL获得的增长大致相同。
我已尝试以功能方式重写它，摆脱循环和可变变量，但性能下降了3-4倍，因此决定保留此版本。
简单但效率低下的建议：
要使其更有效率，您需要通过检查它是否可被较低的质数整除来测试数字是否为质数，这将需要记忆化。最好先等到简单版本运行正常再进行优化 :)
如果这不足以提示您，请告诉我，我会提供完整的示例 - 尽管可能要等到今晚...
这里是我在HubFS上的旧帖子，介绍使用递归序列实现素数生成器。
如果你想要快速实现，可以看看Markus Mottl写的不错的OCaml代码
P.S. 如果你想要迭代10^20以内的素数，建议将D.J. Bernstein的primegen移植到F#/OCaml中 :)
Console.WriteLine不符合 F# 的精神。我建议改用printfn "%i" i。 - Noldorin