使用方案获取每个第 n 个原子不会获取最后一个原子 [英] Getting every nth atom using scheme does not pick up the last atom

问题描述

该程序假设在列表中每三个原子挑选一次.请注意，最后一个原子 'p' 应该被拾取，但它不是.关于为什么没有选择最后一个原子的任何建议.

The program is suppose to pick out every third atom in a list. Notice that the last atom 'p' should be picked up, but its not. Any suggestions as to why the last atom is not being selected.

(define (every3rd lst)
 (if (or (null? lst)            
      (null? (cdr lst)))     
  '()                        
  (cons (car lst)            
        (every3rd (cdr(cdr(cdr lst)))))))


(every3rd '(a b c d e f g h i j k l m n o p))

Value 1: (a d g j m)

谢谢

推荐答案

修复代码(涵盖基本情况)

值得注意的是，Scheme 定义了多个 c[ad]+r 函数，所以你可以使用 (cdddr list) 而不是 (cdr (cdr(cdr列表))):

Fixing your code (covering the base cases)

It's worth noting that Scheme defines a number of c[ad]+r functions, so you can use (cdddr list) instead of (cdr (cdr (cdr list))):

(cdddr '(a b c d e f g h i))
;=> (d e f g h i)

正如其他人已经指出的那样，您的代码存在的问题是它没有考虑所有基本情况.在我看来，您有两个基本案例，第二个有两个子案例:

Your code, as others have already pointed out, has the problem that it doesn't consider all of the base cases. As I see it, you have two base cases, and the second has two sub-cases:

• 如果列表为空，则根本没有元素可取，因此您只能返回空列表.
• 如果列表不为空，那么至少有一个元素要取，你需要取它.但是，当您递归时，有两种可能性:
  • 有足够的元素(三个或更多)，你可以取列表的cdddr；或
  • 元素不够，你取的元素应该是最后一个.

  如果您假设 可以以某种方式处理这两种子情况，那么您可以拥有以下通用结构:

  If you assume that <???> can somehow handle both of the subcases, then you can have this general structure:

  (define (every3rd list)
    (if (null? list)
        '()
        (cons (car list) <???>)))
  

  既然你已经知道如何处理空列表情况，我认为这里一个有用的方法是模糊两个子情况之间的区别，简单地说:recurse on x where x 是列表的 cdddr(如果有)，如果没有，则为空列表."编写一个函数 maybe-cdddr 很容易，该函数返回列表的 cdddr(如果有)，如果没有，则返回空列表":

  Since you already know how to handle the empty list case, I think that a useful approach here is to blur the distinction between the two subcases, and simply say: "recurse on x where x is the cdddr of the list if it has one, and the empty list if it doesn't." It's easy enough to write a function maybe-cdddr that returns "the cdddr of a list if it has one, and the empty list if it doesn't":

  (define (maybe-cdddr list)
    (if (or (null? list)
            (null? (cdr list))
            (null? (cddr list)))
        '()
        (cdddr list)))
  

  > (maybe-cdddr '(a b c d))
  (d)
  > (maybe-cdddr '(a b c))
  ()
  > (maybe-cdddr '(a b))
  ()
  > (maybe-cdddr '(a))
  ()
  > (maybe-cdddr '())
  ()
  

  现在您可以将这些组合起来得到:

  Now you can combine these to get:

  (define (every3rd list)
    (if (null? list)
        '()
        (cons (car list) (every3rd (maybe-cdddr list)))))
  

  > (every3rd '(a b c d e f g h i j k l m n o p))
  (a d g j m)
  

  更加模块化的方法

  先解决更一般的问题通常更容易.在这种情况下，从列表中取出每个 n^th 元素:

  (define (take-each-nth list n)
    ;; Iterate down the list, accumulating elements 
    ;; anytime that i=0.  In general, each
    ;; step decrements i by 1, but when i=0, i
    ;; is reset to n-1.
    (let recur ((list list) (i 0))
      (cond ((null? list) '())
            ((zero? i)    (cons (car list) (recur (cdr list) (- n 1))))
            (else         (recur (cdr list) (- i 1))))))
  

  > (take-each-nth '(a b c d e f g h i j k l m n o p) 2)
  (a c e g i k m o)
  
  > (take-each-nth '(a b c d e f g h i j k l m n o p) 5)
  (a f k p)
  

  一旦你这样做了，就很容易定义更特殊的情况:

  Once you've done that, it's easy to define the more particular case:

  (define (every3rd list)
    (take-each-nth list 3))
  

  > (every3rd '(a b c d e f g h i j k l m n o p))
  (a d g j m)
  

  这样做的好处是，您现在可以更轻松地改进一般情况并维护相同的界面every3rd，而无需进行任何更改.例如，take-each-nth 的实现在递归中使用了一些堆栈空间，但在第二种情况下是非尾调用.通过使用累加器，我们可以以相反的顺序构建结果列表，并在到达列表末尾时返回:

  This has the advantage that you can now more easily improve the general case and maintain the same interface every3rd without having to make any changes. For instance, the implementation of take-each-nth uses some stack space in the recursive, but non-tail call in the second case. By using an accumulator, we can built the result list in reverse order, and return it when we reach the end of the list:

  (define (take-each-nth list n)
    ;; This loop is like the one above, but uses an accumulator
    ;; to make all the recursive calls in tail position.  When 
    ;; i=0, a new element is added to results, and i is reset to
    ;; n-1.  If i≠0, then i is decremented and nothing is added 
    ;; to the results.  When the list is finally empty, the
    ;; results are returned in reverse order.
    (let recur ((list list) (i 0) (results '()))
      (cond ((null? list) (reverse results))
            ((zero? i)    (recur (cdr list) (- n 1) (cons (car list) results)))
            (else         (recur (cdr list) (- i 1) results)))))
  

  这篇关于使用方案获取每个第 n 个原子不会获取最后一个原子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！