Grundlagen der funktionsorientierten Programmierung mit SCHEME/Primzahlfilter

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
<code id="4bd496d2acb43" hidden>
;-- M. Hielscher / Chr. Wagenknecht --
(define random-maker
  (let* ((multiplier 48271)
         (modulus 2147483647)
         (apply-congruence
          (lambda (current-seed)
            (let ((candidate (modulo (* current-seed multiplier) modulus)))
              (if (zero? candidate)
                  modulus
                  candidate))))
         (coerce
          (lambda (proposed-seed)
            (if (integer? proposed-seed)
                (- modulus (modulo proposed-seed modulus)) 19880214))))
  (lambda (initial-seed)
    (let ((seed (coerce initial-seed)))
      (lambda args
        (cond ((null? args)
               (set! seed (apply-congruence seed))
               (/ (- modulus seed) modulus))
              ((null? (cdr args))
               (let* ((proposed-top
                       (ceiling (abs (car args))))
                      (exact-top
                       (if (inexact? proposed-top)
                           (inexact->exact proposed-top)
                           proposed-top))
                      (top
                       (if (zero? exact-top)
                           1
                           exact-top)))
                 (set! seed (apply-congruence seed))
                 (inexact->exact (floor (* top (/ seed modulus))))))
              ((eq? (cadr args) 'reset)
               (set! seed (coerce (car args))))
              (else
               (display "random: unrecognized message")
               (newline))))))))

(require-library 'sisc/libs/srfi/srfi-19)
(import srfi-19)

(define random (random-maker (time-nanosecond (current-time))))
</code>

Zunächst soll unser Filter an einer generierten Liste natürlicher Zahlen getestet werden:

<code id="4b11180069102">
(define natzahlliste
  (lambda (n)
    (if (= n 0)
        (list 0)
        (append (natzahlliste (- n 1)) (list n)))))

(define ungerade?
  (lambda (n)
    (= (modulo n 2) 1)))

(define my-filter
  (lambda (proz ls)
    (cond
      [(null? ls) ()]
      [(proz (car ls)) (cons (car ls) (my-filter proz (cdr ls)))]
      [else
       (my-filter proz (cdr ls))])))
</code>

<eval id="4b1118006b030">
(my-filter ungerade? (natzahlliste 50))
</eval>

In einer ersten Idee müsste der Primzahlprüfer die Teilbarkeit der Zahl <math>n</math> durch alle Vorgänger prüfen und als Teiler nur die <math>1</math> finden.<br />
Nach weiterführenden Überlegungen kann die Suche aber auf ungerade Teiler bis <math>\sqrt{n}</math> beschränkt werden:
<code id="4b1118006a099">
(define primzahl?
  (lambda (n)
    (letrec
        ([prim?
          (lambda (n t)
            (cond
              [(> t (sqrt n)) #t]  
              [(= (modulo n t) 0) #f]                  
              [else
               (prim? n (+ t 2))]))])
      (cond
        [(= n 2) #t]
        [(or (< n 2) (= (modulo n 2) 0)) #f]
        [else        
         (prim? n 3)]))))
</code>

'''Hinweis:''' Mit <tt>letrec</tt> lassen sich ''lokale rekursive'' Datenstrukturen definieren.

<eval id="4b112117825f1">
(my-filter primzahl? (natzahlliste 100))
</eval>

Interessante Untersuchungen lassen sich an Listen mit ''zufälligen'' natürlichen Zahlen vornehmen:

<code id="4b112718adfd2">
(define zufallsliste
  (lambda (bis n)
    (if (= n 0)
        ()
        (cons (+ 1 (random bis)) (zufallsliste bis (- n 1))))))
</code> 

<eval id="4b112718aef77">
(my-filter primzahl? (zufallsliste 1000 100))
</eval>

Zurück zu [[Grundlagen der funktionsorientierten Programmierung mit SCHEME/Prozeduren höherer Ordnung (I)|Prozeduren höherer Ordnung (I)]].