Grundlagen der funktionsorientierten Programmierung mit SCHEME/Primzahlfilter

Wiki-Quelltext dieser Seite.

<language>SchemeJS</language>
<code id="5ba611899520d" hidden>
(define testliste
  (lambda (n)
    (if (= n 0)
        (list 0)
        (cons n (testliste (- n 1))))))
</code>

Zunächst soll unser Filter an einer generierten Liste natürlicher Zahlen getestet werden.<br />
Ergänzen Sie die erforderlichen Prozeduren:

<code id="5a4e1fa996cc7">
(define natzahlliste
  (lambda (n)
    ...))

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

(define my-filter
  (lambda (proz ls)
    ...))
</code>

<check>
(and (equal? (my-filter ungerade? '(1 2 3 4 5)) '(1 3 5))
     (equal? (my-filter ungerade? '(2 4 6 8 10)) '())
     (or (equal? (my-filter (lambda (x) (* 2 x)) (natzahlliste 23)) (my-filter (lambda (x) (* 2 x)) (testliste 23)))
         (equal? (my-filter (lambda (x) (* 2 x)) (natzahlliste 23)) (my-filter (lambda (x) (* 2 x)) (reverse (testliste 23))))))
</check>

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

In einer ersten Idee müsste der Primzahlprüfer die Teilbarkeit der Zahl $n$ durch alle Vorgänger prüfen und als Teiler nur die $1$ finden.<br />

<code id="5a4e1fa996d62">
(define teilerliste
  (lambda (n)
    (teiler-help n (- n 1))))

(define teiler-help
  (lambda (n m)
    ...))

(define primzahl1?
  (lambda (n)
    (and (> n 1) (= (length (teilerliste n)) 1))))
</code>

<check>
(and (equal? (my-filter primzahl1? '(1 2 3 4 5)) '(2 3 5))
     (equal? (my-filter primzahl1? '(2 4 6 8 10)) '(2))
     (or (equal? (my-filter primzahl1? (natzahlliste 23)) (my-filter primzahl1? (testliste 23)))
         (equal? (my-filter primzahl1? (natzahlliste 23)) (my-filter primzahl1? (reverse (testliste 23))))))
</check>

<run id="5a4e1fa996e99">
(my-filter primzahl1? (natzahlliste 100))
</run>

Nach weiterführenden Überlegungen kann die Suche aber auf ungerade Teiler bis $\sqrt{n}$ beschränkt werden:
<code id="5a4e1fa996dec">
(define primzahl2?
  (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.

<run id="5a4e1fa996f4d">
(my-filter primzahl2? (natzahlliste 100))
</run>

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> 

'''Hinweis:''' <tt>(random &lt;max&gt;)</tt> gibt eine Zufallszahl $z$ zurück mit $0 \le z < max$.<br />

<run id="5a4e1fa996fd9">
(my-filter primzahl2? (zufallsliste 1000 100))
</run>

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