使用Dr.racket解决功能性编程问题 [英] Solving a functional programming problem using dr.racket

问题描述

我正在尝试实现一个名为 funPower 的函数，该函数需要一个函数 f ，一个整数 n 并返回该函数f ^ n .例如(((funPower sqrt 2)16)应该返回 2 ，即(sqrt(sqrt 16)).

I am trying to implement a function called funPower, which takes a function f, an integer n and returns the function f^n. For example ((funPower sqrt 2) 16) should return 2, which is (sqrt (sqrt 16)).

到目前为止，这是我所得到的，但是并不能提供正确的输出结果

This is what I have so far but it is not giving me correct output

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

推荐答案

首先，您缺少一对parens.

First, you're missing one more pair of parens.

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

因为(funPower1 f(-n 1))返回要在 x 上调用的函数，如示例所示，将来的参数值((funPower sqrt 2) 16 ).

because (funPower1 f (- n 1)) returns a function to be called on x, the future argument value, as you show with the example, ((funPower sqrt 2) 16).

其次，它是< = 0 ，而不是< = 1 ，并且不应完全调用函数 f 这样的情况:

Second, it's <= 0, not <= 1, and the function f shouldn't be called at all in such a case:

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

现在它可以正常工作了，我们看到它可以将决定推迟到((funPower f n)x)的最终通话时间.但是它确实可以预先做出所有决定- n 是已知的.

Now that it's working, we see that it defers the decisions to the final call time, of ((funPower f n) x). But it really could do all the decisions upfront -- the n is already known.

要实现此目的，我们需要交换(lambda )和(funPower ，以将lambda 推入" .我们这样做，它将成为此类增强的 funPower

To achieve that, we need to swap the (lambda and the (funPower, to push the lambda "in". When we do, it'll become an additional argument to such augmented funPower:

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

现在此完全不同步.第三个争论在哪里?

Now this is completely out of sync. Where's that third argument?

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

这要好一点，但是最初的 fun 是什么?它从何而来?首先必须始终为(lambda(x)x)，否则将不正确.解决方案是使其成为内部定义并使用它，并在我们首次调用它时为其提供正确的参数:

That's a little bit better, but what's the fun, originally? Where does it come from? It must always be (lambda (x) x) at first or else it won't be right. The solution is to make it an internal definition and use that, supplying it the correct argument the first time we call it:

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

通常将这种东西编码为一个名为 let ，

This kind of thing would normally be coded as a named 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)))))))

我们也可以尝试在更简单的情况下创建更简单的功能.例如，如果 n 为 1 :

We could also try creating simpler functions in the simpler cases. For instance, we could return f itself if n is 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)))))))))

通过填充空格来完成它.

Complete it by filling in the blanks.

更多实质性的进一步改进是通过重复平方来使用幂运算-在构造结果函数时，以及在我们构造的函数中使用它！

More substantive further improvement is to use exponentiation by repeated squaring -- both in constructing the resulting function, and to have it used by the function we construct!

这篇关于使用Dr.racket解决功能性编程问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！