Sieve of Eratosthenes 的 Haskell/Scheme 实现

win_hate

lazy scheme

1. 
   
2. (define (integers n)
   
3.   (cons n (integers (+ n 1))))
   
4. 
   
5. (define (sieve seq)
   
6.   (let ((p (car seq)))
   
7.   (cons p (sieve
   
8.            (filter (lambda (x) (not (= 0 (modulo x p)))) (cdr seq))))))
   
9.            
   
10. (define primes (sieve (integers 2)))
    

复制代码

> (list-ref primes 50)
233

win_hate

一个带平方优化的版本

1. 
   
2. (define odd
   
3.   (letrec ((f (lambda (n)
   
4.              (cons n (f (+ n 2))))))
   
5.     (f 3)))
   
6. 
   
7. (define primes
   
8.   (cons 2 (filter primes? odd)))
   
9. 
   
10. (define (primes? n)
    
11.   (define (f ps)
    
12.     (let ((p (car ps)))
    
13.       (cond ((> (* p p) n) #t)
    
14.             ((= (modulo n p) 0) #f)
    
15.             (else (f (cdr ps))))))
    
16.   (f primes))
    

复制代码

win_hate

原帖由 MMMIX 于 2008-9-21 01:59 发表
我觉着 integers 的定义可以优化下
PLT Scheme 实现

#lang lazy

(define (integers n)
  (cons n (integers (+ n 2))))

(define (sieve seq)
  (let ((p (car seq)))
  (cons p (sieve
         ...

说得对，用奇数列相当于在选材上先 filter 了一次。

那个 #lang lazy 在 mzscheme 中好用吗？我这里试了不行。

[ 本帖最后由 win_hate 于 2008-9-21 10:34 编辑 ]

win_hate

谢谢！


用模块之后可以了，但对整个体系还是很模糊。要找个时间把 PLT 的文档好好看一看才行。

1. 
   
2. (module nth (lib "lazy.ss" "lazy")
   
3.   
   
4.   (define odd
   
5.     (letrec ((f (lambda (n)
   
6.                   (cons n (f (+ n 2))))))
   
7.       (f 3)))
   
8.   
   
9.   (define primes
   
10.     (cons 2 (filter primes? odd)))
    
11.   
    
12.   (define (primes? n)
    
13.     (define (f ps)
    
14.       (let ((p (car ps)))
    
15.         (cond ((> (* p p) n) #t)
    
16.               ((= (modulo n p) 0) #f)
    
17.               (else (f (cdr ps))))))
    
18.     (f primes))
    
19.   
    
20.   (define (nth-prime n)
    
21.     (! (list-ref primes n)))
    
22.   
    
23.   (provide nth-prime))
    

复制代码

win_hate

我不是很明白你的意思。

如果直接选 lazy scheme，是可以运行的。我回的第一贴用的就是这个环境

如果把语言选为 module，则得到一条错误。

可能我模块那里没写对？

[ 本帖最后由 win_hate 于 2008-9-21 17:49 编辑 ]

win_hate

我下个官方的 svn 版本捣鼓一下。你用的是那个版本吗？

就我现在这个版本，只要在代码的开头加入

1. 
   
2. (require (lib "lazy.ss" "lazy"))
   

复制代码

则 mzscheme 就变成 lazy 的了。

[ 本帖最后由 win_hate 于 2008-9-21 19:15 编辑 ]

win_hate

没有我可用的版本(XUbuntu)，x86_64 那个是红帽的，估计不好用。

win_hate

svn check out 的版本(11826)，4.1.0.3

现在用 lang 可以用了，谢谢！

[ 本帖最后由 win_hate 于 2008-9-21 22:25 编辑 ]

win_hate

n 比较小的时候用这种方法可能没什么好处。但用大一点的 n，比如 1000， 在我这里测，差别很大。你看看我的截图：

win_hate

学习 Haskell，你的第一个代码我能看明白，第二个就看不懂了。帮我解释一下吧

1. 
   
2. sieve :: [Integer] -> [Integer]
   
3. sieve (x:xs) = x : sieve (xs' ++ xs''')            
   
4.              where
   
5.                 (xs', xs'') = break (>= x*x) xs      
   
6.                 xs''' = filter (\y -> y `mod` x /= 0) xs''
   
7. 
   
8. primes = 2 : sieve [3,5..]
   

复制代码

• xs'++xs'''，中的 ++ 是什么意思？
  
• (xs', xs'') = break (>= x*x) xs，这里是给 xs' 和 xs'' 绑定值吗？如果是，分别绑定了什么？