Lösen eines funktionalen Programmierproblems mit dr.racket

Question

Ich versuche eine aufgerufene Funktion zu implementieren funPower, die eine Funktion f, eine Ganzzahl nund die Funktion zurückgibt f^n. Zum Beispiel ((funPower sqrt 2) 16)sollte 2 zurückgegeben werden , was ist (sqrt (sqrt 16)).

Dies ist, was ich bisher habe, aber es gibt mir nicht die richtige Ausgabe

(define (funPower f n)
  (lambda(x) (if (<= n 1)
            (f x)
            (f (funPower f (- n 1)) x))))

Answer 1

Erstens fehlt Ihnen noch ein Paar Parens.

(define (funPower1 f n)
  (lambda (x) (if (<= n 1)
            (f x)
         ;; (f (   funPower1 f (- n 1)) x))))
            (f ( ( funPower1 f (- n 1)) x)))) )
         ;;     ^^^                          ^^^

da (funPower1 f (- n 1))kehrt eine Funktion zu werden aufgerufen x, die Zukunft Argumentwert, wie Sie mit dem Beispiel zeigen .((funPower sqrt 2) 16)

Zweitens ist es <= 0nicht <= 1und die Funktion fsollte in einem solchen Fall überhaupt nicht aufgerufen werden:

(define (funPower2 f n)
  (lambda (x) (if (<= n 0)
         ;; (f x)      ^^^
               x 
            (f ( ( funPower2 f (- n 1)) x)))) )

Jetzt, da es funktioniert, sehen wir, dass es die Entscheidungen auf die endgültige Anrufzeit von verzögert ((funPower f n) x). Aber es könnte wirklich alle Entscheidungen im Voraus treffen - das nist bereits bekannt.

Um dies zu erreichen, müssen wir das (lambdaund das tauschen (funPower, um das Lambda "hinein" zu schieben . Wenn wir das tun, wird es ein zusätzliches Argument für eine solche Erweiterung funPower:

(define (funPower3 f n)
  (if (<= n 0) (lambda (x) 
               x )
    (funPower3 f (- n 1) (lambda (x) (f x)))) )

Dies ist jetzt nicht mehr synchron. Wo ist das dritte Argument?

(define (funPower4 f n fun)
  (if (<= n 0) fun
    (funPower4 f (- n 1) (lambda (x) (fun (f x)))) ))

Das ist ein bisschen besser, aber was ist das funursprünglich? Woher kommt das? Es muss immer (lambda (x) x)zuerst sein, sonst wird es nicht richtig sein. Die Lösung besteht darin, daraus eine interne Definition zu machen und diese zu verwenden und beim ersten Aufruf das richtige Argument anzugeben:

(define (funPower5 f n)
  (define (loop n fun)
    (if (<= n 0) fun
      (loop (- n 1) 
            (lambda (x) (fun (f x))))))
  (loop n (lambda (x) x)))

Diese Art von Dingen wird normalerweise als benannt codiert let,

(define (funPower5 f n)
  (let loop ((n  n) 
             (fun (lambda (x) x)))
    (if (<= n 0) fun
      (loop (- n 1) 
            (lambda (x) (fun (f x)))))))

In den einfacheren Fällen könnten wir auch versuchen, einfachere Funktionen zu erstellen. Zum Beispiel könnten wir zurückkehren fselbst wenn nist 1:

(define (funPower6 f n)
  (cond 
    ((zero? n) .....)
    ((= n 1)   .....)
    ((< n 0)   .....)
    (else
      (let loop ((n  n) 
                 (fun .....))
        (if (= n .....) fun
          (loop (- n 1) 
            (lambda (x) (fun (f x)))))))))

Vervollständigen Sie es, indem Sie die Lücken ausfüllen.

Eine wesentlichere weitere Verbesserung besteht darin, die Exponentiation durch wiederholtes Quadrieren zu verwenden - sowohl bei der Konstruktion der resultierenden Funktion als auch bei der Verwendung durch die von uns konstruierte Funktion!

Answer 2

Versuche dies:

(define funpow
  (lambda (f n)
    ((lambda (s) (s s n (lambda (x) x)))
     (lambda (s n o)
       (if (zero? n)
           o
           (s s (- n 1)
              (lambda (x)
                (o (f x)))))))))

    
(define sqrt_2 (funpow sqrt 2))
(define pow2_2 (funpow (lambda (x) (* x x)) 2))

(sqrt_2 16)
(pow2_2 2)