scheme - 比较两个列表，如果它们不相等则返回 false

Question

我想请求您帮助完成下面的代码，条件是测试列表 ws 和 vs 是否不相等。如果它们不相等，则返回文本 false(#f)，否则处理下面的代码。我盯着履行变量 len1 和 len2，它们正在计算两个列表的长度。当我运行它时，我收到此错误:lambda:在以下内部定义序列之后没有表达式:lambda我做错了什么？

(define (weighted-sum . ws)
  (define (sub . vs)
    (let ((len1 (length ws)) (len2 (length vs)))
    (if (not (equal? (len1 len2) '#f))
    (foldl
     (lambda (i j res) (+ res (* i j)))
     0
     ws vs)))
   sub)

感谢您的帮助。

Answer 1

length 在Scheme 中几乎总是一种反模式。

length 是一个 O(n) 操作，调用两次，然后调用另一个 O(n) 操作，foldl，导致加权和的O(3n)过程 - 远离理想的最小值O(n) 。 foldl 对于许多线性计算来说是一个很好的候选者，但是由于长度匹配的要求，您已经创建了一些圆孔中的方钉情况。

使用命名let和match*，我们将weighted-sum写为O(n) 计算-

#lang racket

(define ((weighted-sum . ws) . vs) ;; curried form syntactic sugar 
  (let loop ((acc 0)
             (ws ws)
             (vs vs))
    (match* (ws vs)
      ;; both lists have at least one value
      [((list w ws ...) (list v vs ...))
       (loop (+ acc (* w v))
             ws
             vs)]
      ;; both lists are empty
      [((list) (list))
       acc]
      ;; any other case
      [(_ _)
       #f])))

当然 match* 是一个非常奇特的宏，所以我将向您展示如何使用简单的 cond 重写 weighted-sum表达。准备好逻辑推理帽:条件子句的顺序在这里非常重要 -

(define ((weighted-sum . ws) . vs)
  (let loop ((acc 0)
             (ws ws)
             (vs vs))
    (cond
      ;; both lists are empty
      [(and (null? ws)
            (null? vs))
       acc]
      ;; at least one list is empty
      [(or (null? ws)
           (null? vs))
       #f]
      ;; inductive: both lists have at least one value
      [else
       (loop (+ acc (* (car ws)
                       (car vs)))
             (cdr ws)
             (cdr vs))])))

两个程序具有相同的输出 -

((weighted-sum 1 2 3) 1 2 3)
;; 14

((weighted-sum 1 2 3) 1 2)
;; #f

((weighted-sum 1 2) 1 2 3)
;; #f

((weighted-sum))
;; 0