Curry-Skip方案

Question

我必须编写一个名为curry-skip的方案函数，该函数以递归方式返回列表的第n个元素，使得

(((curry-skip 1) 'foo) 'bar) => bar

我似乎想不出如何递归地做这件事。我对Scheme还很陌生，所以如果有任何帮助，我将不胜感激！谢谢

Answer 1

在看了你的例子之后，我写了下面的内容。它看起来相当简单，因此我无法解释它是如何产生的。

(define (curry-skip n) 
    (lambda (v) (if (= n 0) 
                    v 
                    (curry-skip (- n 1)))))

Answer 2

我想你这里有3个案例：

1. n>0 -向下递归到n=0
2. n=0 -记住参数，因为这是您需要返回的最后一个值；记住是通过闭包
3. 完成的；否则-忽略参数直到完成，然后最终返回记住的值

所以

(define (res val)                                ; [procedure used for case 2 - n=0]
  (define (res0 . x) (if (null? x) val res0))    ; [case 3]
  res0)

(define (curry-skip n) 
  (cond
    ((< n 0) (error "n is negative"))
    ((= n 0) res)                                ; [case 2 - n = 0]
    (else    (lambda x (curry-skip (- n 1))))))  ; [case 1 - n > 0]

然后

-> (((curry-skip 0) 'foo))
'foo
-> ((((curry-skip 0) 'foo) 'bar))
'foo
-> ((((curry-skip 1) 'foo) 'bar))
'bar
-> (((((curry-skip 0) 'foo) 'bar) 'baz))
'foo
-> (((((curry-skip 1) 'foo) 'bar) 'baz))
'bar
-> (((((curry-skip 2) 'foo) 'bar) 'baz))
'baz

与你的问题相比，我的答案多了一对括号，但这是我能得到的最接近的结果。

Answer 3

(define (curry-skip n)
  (if (zero? n)
      (lambda (x) x)
      (let ((rest (curry-skip (- n 1))))
        (lambda (x) rest))))

您想要在返回的lambda的之外计算(- n 1) cases ！因此，在上面的示例中，当n为零时，只返回一个参数lambda；但是，当n为正时，计算(- n 1)情况并返回一个忽略其参数的lambda，只返回rest。

注意，虽然不是你问题的一部分，但与评论有关，如果你需要一个真正的curry，就像ML一样，你需要语法帮助，如下所示：

(define-syntax curry*
  (syntax-rules ()
    ((_ (a) body ...) (lambda (a) body ...))
    ((_ (a b ...) body ...)
     (lambda (a) (curry* (b ...) body ...)))))

注意递归如何为每个a, b, …创建词法环境，以便可以正确地计算body。curry-skip没有这样的需求。

下面是一些代码，用于处理关于在返回的lambda中执行“curry-skip”的注释。在lambda外部进行递归只发生一次，创建一个闭包；在lambda内部进行递归将在每次调用时创建闭包。

(define (curry-skip-o n)
  (if (zero? n)
      (lambda (x) x)
      (let ((rest (curry-skip-o (- n 1))))
        (lambda (x) rest))))

(define (curry-skip-i n)
  (if (zero? n)
      (lambda (x) x)
      (lambda (x) (curry-skip-i (- n 1)))))

(define (run skipper r n)
  (let ((f (skipper n)))
    ;; Repeat 'r' times with 'f'
    (let rep ((r r))
      (unless (zero? r)
        ;; Exhaust f
        (let rep ((i 0) (f f))
          (if (< i n)
              (rep (+ i 1) (f i))
              (f 0)))
        (rep (- r 1))))))

> (time (run curry-skip-o 10000 10000))            ;; create ~10^4 closures
running stats for (run curry-skip-o 10000 10000):
    no collections
    376 ms elapsed cpu time, including 0 ms collecting
    376 ms elapsed real time, including 0 ms collecting
    160032 bytes allocated
> (time (run curry-skip-i 10000 10000))            ;; create ~10^8 closures
running stats for (run curry-skip-i 10000 10000):
    191 collections
    1587 ms elapsed cpu time, including 965 ms collecting
    1588 ms elapsed real time, including 966 ms collecting
    1599840048 bytes allocated