[plt-scheme] Getting started with Scheme: How can I improve my code for generating prime numbers?

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Sun Aug 2 15:06:05 EDT 2009

Let me quickly respond with a few comments and a snippet of code.

1. Functional programming is something you can do in every  
programming language: assembly, c, c++, java, python, you name it. I  
bet I could do it in cobol.

2. When you do program functionally, it is not about translating some  
snippet of code from one language to another. In case you know a  
foreign language, doing so is like translating English sentences into  
say German word by word. In all likelihood, it makes no sense  

3. If your task is to sieve through __all__ natural numbers so that  
you get all prime numbers, you program with the object that comprises  
__all__ naturals and get the object of __all__ primes. Picking the  
first n is boring and it is only done because the typical Python  
programmer isn't trained to think of the full range of possibilities.  
(See 1 -- functional programming can be done in pyton). Here is the  
code for that:

#lang lazy ; this is the lazy scheme dialect available with plt  
scheme, both in drscheme and in mzscheme

;; all natural numbers
(define nats$ (cons 0 (map add1 nats$)))

;; all primes
;; Stream[Number] -> Stream[Number]
;; generative: eliminate all first elements from the rest of the  
stream, then recur
(define (sieve s$)
   (define fst (first s$))
   (cons fst (sieve (filter (lambda (m) (not (= (remainder m fst)  
0))) s$))))

(define primes$ (sieve (rest (rest nats$))))

;; --- for you only ---
;; print the first n primes
(define (print-primes n)
   (for-each (lambda (x) (display x) (newline)) (!list (take n primes 

(print-primes 1000)

Here is how this runs:

[home] $ mzscheme sieve.ss
1.827u 0.205s 0:02.18 92.6%	0+0k 0+1io 0pf+0w

4. Now if you want to learn Scheme programming, you're right in that  
Scheme programmers think functionally a lot of the time. But you also  
need ot know that they throw in assignment statements, exceptions,  
continuations, and other effects when needed. Scheme is a full- 
spectrum language.

I'll take a closer look at your code now. -- Matthias

On Aug 1, 2009, at 1:35 PM, SiWi wrote:

> Hello PLT Scheme community,
> this is my first post here, so please excuse any mistakes.
> I'm 16 years old and so far my programming experience has mainly been
> in Python.
> To learn about functional programming, I just started with Scheme.
> For training I tried to convert some prime number generator code from
> Python to Scheme.
> It's using a sieve algorithm.
> The problem is that my Scheme code is about 1000-10000 times slower
> than my Python code.
> I would greatly appreciate it if you could give me some hints on how
> to improve my code.
> Python code:
> def primes(n):
> 	sieve=[True for x in range(3,n+1,2)]
> 	root=n**0.5
> 	length=len(sieve)
> 	for i in range(len(sieve)):
> 		x=2*i+3
> 		if x>root:
> 			break
> 		if sieve[i]:
> 			for j in range((x*x-x)/2+i,length,x):
> 				sieve[j]=False
> 	return [2]+[x*2+3 for x in range(length) if sieve[x]]
> Scheme code:
> (define (primes n)
>   (letrec ((primes-go (lambda (n lst i x nroot) (if (> x nroot)
>                                                   lst
>                                                   (let ((temp-lst  
> (lst-
> remove lst 0 (+ (/ (- (* x x) x) 2) i) x)))
>                                                   (primes-go n temp-
> lst (+ i 1) (+ (* 2 i) 3) nroot)))))
>            (lst-remove (lambda (lst i goal step) (if (null? lst)
>                                                         '()
>                                                         (if (= goal i)
>                                                             (cons #f
> (lst-remove (cdr lst) (+ i 1) (+ goal step) step))
>                                                             (cons (car
> lst) (lst-remove (cdr lst) (+ i 1) goal step))))))
>            (list-bool (lambda (n i) (if (>= i n)
>                                         '()
>                                         (cons #t (list-bool n (+ i
> 2))))))
>            (filter (lambda (lst final i length) (if (>= i length)
>                                          final
>                                          (if (list-ref lst i)
>                                              (filter lst (append final
> (list (+ (* 2 i) 3))) (+ i 1) length)
>                                              (filter lst final (+ i 1)
> length))))))
>     (filter (primes-go n (list-bool (+ n 1) 3) 0 3 (sqrt n)) (list 2)
> 0 (length (list-bool (+ n 1) 3)))))
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme

Posted on the users mailing list.