scheme - 为什么我的 pair 输出中出现 mcons 符号？

Question

我尝试在 Scheme 中实现扩展的 Euler 算法，并找到了正确的结果，但是我的主要目标是将解决方案作为一对来获得。但我不明白为什么mcons我的一对前面有一个符号。

这是我的功能和输出

(define ax+by=1 
  (lambda (a b)
    (if (= a 0)
        (cons 0 1)
        (let ((pair (ax+by=1 (remainder b a) a)))
          (cons (- (cdr pair)
                   (* (quotient b a) (car pair)))
                (car pair))))))

 ; > (ax+by=1 17 13)
 ; (mcons -3 4)

我需要一个建议才能以(-3 4).

标签： schemeracket

Answer 1

(define ax+by=1
  (lambda (a b)
    (if (= a 0)
        (list 0 1)
        (let ((pair (ax+by=1 (remainder b a) a)))
          (cons (- (cadr pair)
                   (* (quotient b a) (car pair)))
                (list (car pair)))))))
 ; > (ax+by=1 17 13)
 ; '(-3 4)

您的“问题”是您的函数返回了一个最后一个元素为 NOT 的 cons-cell '()。列表是最后一个元素为 的任何 cons-cells 链nil。

如果您的代码有(cons 3 4)，它会返回(3 . 4)。或者在你的符号中（它不是 Racket，不是吗？或者是 Racket 的子方言？(mcons 3 4)。为了使它成为一个正常的列表，它必须成为(cons 3 (cons 4 '()))完全一样的(list 3 4)。list接受参数并'()在最后一个consescons细胞。

(define ax+by=1
  (lambda (a b)
    (if (= a 0)
        (cons 0 (cons 1 '()))
        (let ((pair (ax+by=1 (remainder b a) a)))
          (cons (- (cadr pair)
                   (* (quotient b a) (car pair)))
                (cons (car pair) '()))))))

超级懒的解决方案

或者，比方说，你超级懒惰，你看到你的旧函数实际上做了它应该做的——只有输出格式必须从对更改为列表。

使用此函数，您可以将对转换为列表：

(define (pair->list p)
  (list (car p) (cdr p))) ; just list the components of pair

然后你可以使用你的旧函数 - 未修改 - 然后是转换器函数并围绕它包装一个函数定义 - 即使使用相同的名称（但是，这对于可读性来说真的很糟糕！ - 然而，有趣的是，这适用于 Racket ... ）。

(define ax+by=1
  (lambda (a b)
    ;; your old function verbatim as inner `ax+by=1`:
    (define ax+by=1 
      (lambda (a b)
        (if (= a 0)
            (cons 0 1)
            (let ((pair (ax+by=1 (remainder b a) a)))
              (cons (- (cdr pair)
                       (* (quotient b a) (car pair)))
                    (car pair))))))
    ;; the transformer function verbatim:
    (define (pair->list p)
      (list (car p) (cdr p)))
    ;; call both inner functions in combination!
    (pair->list (ax+by=1 a b)))) 
    ;; `pair->list` transforms your answer into the correct list form!

最后一个版本值得注意的是，在 的最后一个函数调用中ax+by=1，解释器/编译器“知道”内部函数是指内部函数而不是外部函数（否则外部函数会一次又一次地调用自身，并在无限循环）。这是可能的，因为内部函数名绑定“遮蔽”了外部函数名绑定。

但是，我认为它的风格非常糟糕，因为人类读者可能会对内部函数和外部函数之间的相同名称感到非常困惑。尽管如此，我发现找到一种不修改现有代码的方法很有趣，只需添加一些东西以使事情正常工作，甚至使用预期的旧名称 - 这样结果正是预期的结果。

但肯定我给出的第一个解决方案更好 - 不可能误解代码和混淆事物 - 并直接构建结果列表。