0

我正在使用 Racket ISL+ 编写一个计算一系列结构的递归。如果结构失败了一些参数，我想返回一个#false. 但是，在递归期间的某个时刻，我知道计算机正在获取1 + 1 + 1 + 1 + 1 + 1 + #false，这给了我一个错误。

有没有办法让我声明如果发现错误只是#false从原始调用中返回一个值？

4

1 回答 1

2

当一个值从某个递归过程深处的过程返回时，接收该值的过程必须能够处理它。如果递归过程可以返回两种不同类型中的任何一种，例如布尔值或数字，则该过程将需要在使用需要单一类型的过程处理返回值之前对其进行测试。

使用延续

有可能获得一个延续，然后使用它来逃避递归过程。这可能不是 OP 正在寻找的解决方案；我不相信 HTDP 学生语言提供了一种获得延续的方法。在普通的 Racket 中，您可以使用它call/cc来获取延续：

(define (count-numbers-or-f xs)
  (call/cc
   (lambda (break)
     (define (loop xs)
       (cond ((null? xs) 0)
             ((number? (car xs))
              (+ 1 (loop (cdr xs))))
             (else (break #f))))
     (loop xs))))

这不是开发延续细节的地方，而是简单地call/cc安排它，以便break在上面的代码中是一个转义过程，当被调用时，它将其参数（#f此处）返回到关于调用的计算的延续call/cc. 这里，当输入的第一个元素是 a 时number?，将输入的其余部分计数的结果加 1；但是，当输入的第一个元素不是 a number?（并且输入不是空列表）时，break调用该过程。当在控制break描述的递归过程中被调用时loop跳转到那个延续，它在调用之后call/cc，从而转义递归过程；价值#f被赋予延续，所以#f然后由count-numbers-or-f.

做没有延续

延续是从循环中实现这种非本地退出的经典方法，但您可以通过一些精心设计，使用较少异国情调的方式获得类似的结果：

(define (count-numbers-or-f-1 xs)
  (cond ((null? xs) 0)
        ((not (number? (car xs))) #f)
        (else
         (let ((r (count-numbers-or-f-1 (cdr xs))))
           (if (number? r)
               (+ 1 r)
               #f)))))

在这里，如果 car ofxs不是数字（xs也不是空列表），则#f返回给前一个调用者。否则r表示调用count-numbers-of-f-1cdr 的结果xs。如果r不是数字（因为后续调用者遇到了非数字元素并返回#f），则#f返回。否则，加法过程会增长。

这样做的结果是，如果遇到不是数字的元素，#f则立即通过所有先前的堆栈帧传回原始调用，否则执行求和。设计这样的程序很容易犯错误，这样它们看起来可以工作，但最终会通过遍历所有输入（或更糟）来做很多不必要的工作。请参阅答案的结尾，以讨论此处可能出现的问题。

比较

上述任何一个定义都将起作用：

scratch.rkt> (count-numbers-or-f '(1 2 3 4))
4
scratch.rkt> (count-numbers-or-f '(1 2 x 3 4))
#f
scratch.rkt> (count-numbers-or-f-1 '(1 2 3 4))
4
scratch.rkt> (count-numbers-or-f-1 '(1 2 x 3 4))
#f

以下是第二个版本的一些痕迹：

scratch.rkt> (count-numbers-or-f-1 '(1 2 3 4 5))
>(count-numbers-or-f-1 '(1 2 3 4 5))
> (count-numbers-or-f-1 '(2 3 4 5))
> >(count-numbers-or-f-1 '(3 4 5))
> > (count-numbers-or-f-1 '(4 5))
> > >(count-numbers-or-f-1 '(5))
> > > (count-numbers-or-f-1 '())
< < < 0
< < <1
< < 2
< <3
< 4
<5
5

scratch.rkt> (count-numbers-or-f-1 '(1 2 3 x 4 5))
>(count-numbers-or-f-1 '(1 2 3 x 4 5))
> (count-numbers-or-f-1 '(2 3 x 4 5))
> >(count-numbers-or-f-1 '(3 x 4 5))
> > (count-numbers-or-f-1 '(x 4 5))
< < #f    ; returned from (count-numbers-or-f-1 '(x 4 5))
< <#f    ; returned from (count-numbers-or-f-1 '(3 x 4 5))
< #f    ; returned from (count-numbers-or-f-1 '(2 3 x 4 5))
<#f    ; returned from (count-numbers-or-f-1 '(1 2 3 x 4 5))
#f    ; the actual value printed to the REPL

可以看到，当遇到失败元素时，递归立即结束，但控制仍需通过之前的堆栈帧传回。使用call/cc该控件的版本只需从递归过程中逃脱，而无需通过任何先前的帧。

这是第一个过程的一个版本，使用call/cc它进行了修改，以便可以跟踪递归过程：

(define (count-numbers-or-f xs)
  (call/cc
   (lambda (k)
     (loop xs k))))

(define (loop xs break)
  (cond ((null? xs) 0)
        ((number? (car xs))
         (+ 1 (loop (cdr xs) break)))
        (else (break #f))))

这里有一个trace，显示当#f返回时，直接返回，不经过前面的栈帧。遇到loop过程根本不返回；#f而是loop调用break过程，传递#f给它。该break过程跳转到计算的继续，返回#f到该点。由于延续在count-numbers-or-f过程结束时进行计算，#f因此只是从count-numbers-or-f.

scratch.rkt> (count-numbers-or-f '(1 2 3 x 4 5))
>(count-numbers-or-f '(1 2 3 x 4 5))
>(loop '(1 2 3 x 4 5) #<procedure>)
> (loop '(2 3 x 4 5) #<procedure>)
> >(loop '(3 x 4 5) #<procedure>)
> > (loop '(x 4 5) #<procedure>)  ; loop does not return
<#f  ; the value returned by (count-numbers-or-f '(1 2 3 x 4 5))
#f  ; the actual value printed to the REPL

会出什么问题？

一个设计良好的递归过程在这里可以做得很好，但很容易实现一个设计不佳的解决方案，这可能会产生严重的性能问题。

本节将展示设计欠佳的情况下，事情会如何偏离轨道。以下所有程序的工作原理是它们返回正确的结果，但它们具有不同的性能特征，其中最差的实际上是不可用的。要点应该是，至少在一系列预期输入中测试新程序以检查意外情况是很重要的。可能的第二个要点是应该仔细考虑过程定义中的多个递归调用。帮助测试的一个很好的工具是trace；在 Racket 中，您可以(require racket/trace)然后(trace my-procedure)进行检测my-procedure，以便my-procedure使用过程跟踪对任何调用进行注释。这就是生成此答案中的痕迹的方式。

我们已经看到了count-numbers-or-f-1上面的痕迹，表明当遇到失败的元素时，它#f会传递回之前的调用者，直到到达原始调用。

考虑这个实施不佳的版本：

(define (count-numbers-or-f-2 xs)
  (if (null? xs)
      0
      (let ((x (car xs))
            (r (count-numbers-or-f-2 (cdr xs))))
        (if (and (number? x) (number? r))
            (+ 1 r)
            #f))))

在这里，由于count-numbers-or-f-2在检查剩余计算的结果是否为 a之前调用了number?，因此递归过程继续进行，直到到达基本情况(null? xs)。当遇到输入失败时，这根本没有帮助：

scratch.rkt> (count-numbers-or-f-2 '(1 2 3 x 4 5))
>(count-numbers-or-f-2 '(1 2 3 x 4 5))
> (count-numbers-or-f-2 '(2 3 x 4 5))
> >(count-numbers-or-f-2 '(3 x 4 5))
> > (count-numbers-or-f-2 '(x 4 5))
> > >(count-numbers-or-f-2 '(4 5))
> > > (count-numbers-or-f-2 '(5))
> > > >(count-numbers-or-f-2 '())
< < < <0
< < < 1
< < <2
< < #f
< <#f
< #f
<#f
#f

现在考虑这个试图解决最后一个问题的真正糟糕的实现。在将其余计算的结果添加到最终结果之前，这里会检查其余计算的结果。这在输入包含失败元素时有效；但是在计算整个输入的情况下，count-numbers-or-f-3会调用两次，从而导致指数时间复杂度。

(define (count-numbers-or-f-3 xs)
  (if (null? xs)
      0
      (if (and (number? (car xs))
               (number? (count-numbers-or-f-3 (cdr xs))))
          (+ 1 (count-numbers-or-f-3 (cdr xs)))
          #f)))

输入失败的情况看起来很好：

scratch.rkt> (count-numbers-or-f-3 '(1 2 3 x 4 5))
>(count-numbers-or-f-3 '(1 2 3 x 4 5))
> (count-numbers-or-f-3 '(2 3 x 4 5))
> >(count-numbers-or-f-3 '(3 x 4 5))
> > (count-numbers-or-f-3 '(x 4 5))
< < #f
< <#f
< #f
<#f
#f

但是，如果输入应该被计算在内，事情就会变得非常糟糕。事实上，这是错误的，我不得不使用较小的输入来在合理的空间内说明该过程：

>(count-numbers-or-f-3 (1 2 3))
> (count-numbers-or-f-3 '(2 3))
> >(count-numbers-or-f-3 '(3))
> > (count-numbers-or-f-3 '())
< < 0
> > (count-numbers-or-f-3 '())
< < 0
< <1
> >(count-numbers-or-f-3 '(3))
> > (count-numbers-or-f-3 '())
< < 0
> > (count-numbers-or-f-3 '())
< < 0
< <1
< 2
> (count-numbers-or-f-3 '(2 3))
> >(count-numbers-or-f-3 '(3))
> > (count-numbers-or-f-3 '())
< < 0
> > (count-numbers-or-f-3 '())
< < 0
< <1
> >(count-numbers-or-f-3 '(3))
> > (count-numbers-or-f-3 '())
< < 0
> > (count-numbers-or-f-3 '())
< < 0
< <1
< 2
<3
3

这是一个可用于对上述过程进行计时的过程：

(define (time-test f xs)
  (collect-garbage 'major)
  (time (f xs)))

我使用了一个包含 800,001 个数字的列表进行测试，并'x在列表中间放置了一个。count-numbers-or-fusing 延续执行得最好：

scratch.rkt> (time-test count-numbers-or-f
                        (append (build-list 400000 values)
                                '(x)
                                (build-list 400000 values)))
cpu time: 1 real time: 1 gc time: 0
#f

与count-numbers-or-f-1遇到失败输入时结束递归相比，第一个版本由于使用延续的立即转义而更快一些：

scratch.rkt> (time-test count-numbers-or-f-1
                        (append (build-list 400000 values)
                                '(x)
                                (build-list 400000 values)))
cpu time: 5 real time: 5 gc time: 0
#f

即使遇到失败的输入也会遍历所有输入的坏版本更糟糕：

scratch.rkt> (time-test count-numbers-or-f-2
                        (append (build-list 400000 values)
                                '(x)
                                (build-list 400000 values)))
cpu time: 28 real time: 28 gc time: 9
#f

看起来更好的非转义实现，count-numbers-or-f-1比count-numbers-or-f（使用延续）慢约 5 倍，而实现不佳的实现比 .count-numbers-of-f-2慢约 28 倍count-numbers-or-f。但至少所有这些实现的时间复杂度大致为O(n)。最糟糕的版本count-numbers-or-f-3是O(2ⁿ)。Universe 中没有足够的时间来等待此过程对包含 800,001 个元素的列表进行操作。我们将不得不使用更小的输入：

scratch.rkt> (time-test count-numbers-or-f-6 (build-list 25 values))
cpu time: 576 real time: 576 gc time: 0
25
scratch.rkt> (time-test count-numbers-or-f-6 (build-list 26 values))
cpu time: 1159 real time: 1159 gc time: 0
26
scratch.rkt> (time-test count-numbers-or-f-6 (build-list 27 values))
cpu time: 2314 real time: 2314 gc time: 0
27

在这里您可以看到，将输入列表的大小增加 1 个元素大约会使最坏情况下完成计算的时间增加一倍，而那些最坏情况正是您希望完成计算的那些情况，即当您想要计算列表中有多少个数字。

于 2021-04-07T07:09:13.937 回答