scheme - 为什么我的对输出中出现 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) 形式的答案。

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)

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

如果您的代码执行 (cons 3 4)，它会返回 (3 . 4)。或者在你的符号中(它不是 Racket，不是吗？还是 Racket 的一个子方言？(mcons 3 4)。要使其成为普通列表，它必须变为 (cons 3 (cons 4 '())) ，这与 (list 3 4) 完全相同。 list 获取参数并在其最后一个 cons 单元格中的 '() 上使用它们。

(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) '()))))))

super 懒惰的解决方案

或者，假设您 super 懒惰，您发现您的旧函数实际上做了它应该做的事情——只是输出格式必须从 pair 更改为 list。

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

(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 的最后一个函数调用中，解释器/编译器“知道”是指内部函数而不是外部函数(否则外部函数会一次又一次地调用自身，在无限循环中传递给定的参数)。这是可能的，因为内部函数名绑定(bind)“遮蔽”了外部函数名绑定(bind)。

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

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