Resolvendo um problema de programação funcional usando dr.racket

Question

Estou tentando implementar uma função chamada funPower, que leva uma função f, um inteiro ne retorna a função f^n. Por exemplo, ((funPower sqrt 2) 16)deve retornar 2 , que é (sqrt (sqrt 16)).

Isso é o que eu tenho até agora, mas não está me dando uma saída correta

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

Answer 1

Primeiro, você está faltando mais um par de parênteses.

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

porque (funPower1 f (- n 1))retorna uma função a ser chamada x, o valor do argumento futuro, como você mostra com o exemplo ,.((funPower sqrt 2) 16)

Em segundo lugar, é <= 0, não <= 1, e a função fnão deve ser chamada em tal caso:

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

Agora que está funcionando, vemos que adia as decisões para a hora da chamada final, de ((funPower f n) x). Mas ele realmente poderia tomar todas as decisões antecipadamente - o njá é conhecido.

Para conseguir isso, precisamos trocar o (lambdae o (funPower, para empurrar o lambda "para dentro" . Quando o fizermos, isso se tornará um argumento adicional para tal funPower:

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

Agora, isso está completamente fora de sincronia. Onde está o terceiro argumento?

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

Isso é um pouco melhor, mas o que é fun, originalmente? De onde isso vem? Deve ser sempre (lambda (x) x)primeiro ou então não estará certo. A solução é torná-la uma definição interna e usá-la, fornecendo-lhe o argumento correto na primeira vez que a chamarmos:

(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)))

Esse tipo de coisa normalmente seria codificado como um nome 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)))))))

Também podemos tentar criar funções mais simples nos casos mais simples. Por exemplo, podemos retornar a fsi mesmo se nfor 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)))))))))

Conclua preenchendo os espaços em branco.

Uma melhoria adicional mais substantiva é usar a exponenciação por quadratura repetida - tanto na construção da função resultante, quanto para tê-la usada pela função que construímos!

Answer 2

tente isto:

(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)