Scheme

Question

我一直在尝试解决 SICP 的练习 2.20，其中引入了 "dotted-tail" 符号。我的问题是，我的函数 returns 不是返回一个包含结果的正确列表，而是一个嵌套列表。我知道我调用 cons 的方式有问题，但我仍然不知道如何解决这个问题。

所以这是我的函数：

(define (same-parity first . items)

  (define (speccar items)
    (cond ((null? items) 2) 
          ((not (pair? items)) (modulo items 2))
          (else (modulo (car items) 2))))

  (define (iter-parity first items result)
    (let ((parityFirst (modulo first 2)) (samepar (speccar items)))
      (if (null? items)
          result
          (if (= parityFirst samepar)
              ;; This next line is where the problem is...
              (iter-parity first (cdr items) (cons (list result) (list (car items))))
              (iter-parity first (cdr items) result)))))

  (iter-parity first items first))

测试：

(same-parity 1 2 3 4 5)
((((1) 3)) 5)

现在，我阅读了以下处理类似问题的答案：

Cons element to list vs cons list to element in Scheme

How to use 'cons' without generating nested lists in Scheme?

他们当然清楚问题出在哪里，但是如何真正实施正确的解决方案呢？并且，如果可能的话，Scheme 中 "thinking" 避免这些 traps/pitfalls 的正确方法是什么？

Answer 1

您错误地构建了输出列表 - 请记住：cons 的第一个参数应该是当前元素，第二个参数应该是结果列表。

此外，鉴于您使用的是尾递归，您必须 reverse 最后的输出以保留与原始列表中相同的顺序。试试这个：

(define (same-parity first . items)
  (define (speccar items)
    (cond ((null? items) 2) 
          ((not (pair? items)) (modulo items 2))
          (else (modulo (car items) 2))))
  (define (iter-parity first items result)
    (let ((parityFirst (modulo first 2))
          (samepar (speccar items)))
      (if (null? items)
          (reverse result)
          (if (= parityFirst samepar)
              (iter-parity first
                           (cdr items)
                           (cons (car items) result))
              (iter-parity first
                           (cdr items)
                           result)))))  
  (iter-parity first items (list first)))

如果我们使用内置程序，上述解决方案可以大大简化（不要重新发明轮子！）。这是在Scheme中编写程序的推荐方式——坚持函数式风格：

(define (same-parity head . tail)
  (if (even? head)
      (filter even? (cons head tail))
      (filter  odd? (cons head tail))))

无论哪种方式，它都按预期工作：

(same-parity 1 2 3 4 5)
=> '(1 3 5)

Scheme - 正确使用 cons 创建列表

Scheme - Using cons properly to create lists

racket

sicp