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

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  
whatsoever.

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