0

该程序获取一个重复元素的列表，例如L = (a a a b b b c c c d)，并输出一个项目列表和重复次数，例如((a 3)(b 3)(c 3) d) 

(define counter 0)
(define (compress liste)
(if (or (null? liste) (null? (cdr liste)))
   liste
(let ((compressed-cdr (compress (cdr liste)))) 
   (if (equal? (car liste) (car compressed-cdr))
   ((+ counter 1) compressed-cdr)
  ((cons (car liste) counter) (= counter 0) (compressed-cdr))))
                       ))

但是，我收到此错误：

错误：应用程序：不是程序；期望一个可以应用于给
定参数的过程：1个参数...

错误出现在第二个 if 条件的真谓词上。

4

3 回答 3

1

我很难弄清楚代码中的问题所在。我尝试了以下似乎可行的方法。

(define (compress liste)

  (define (helper in prev out)
     (if (null? in)
        (list (list (car out) (length out)))
        (if (equal? prev (car in))
          (helper (cdr in) prev (append out (list (car in))))
          (cons (list (car out) (length out)) (compress in)))))


    (if (null? liste)
      '()
      (helper (cdr liste) (car liste) (list (car liste))))
      )

它用于helper收集匹配项目的输出。当它发现不匹配时，它会调用 main 函数来处理列表的其余部分。helper简单地将其结果添加到从 main 函数获得的结果中。

稍微改进的版本：

(define (compress liste)

  (define (helper in prev out)
     (if (null? in)
        (list (list prev out))
        (if (equal? prev (car in))
          (helper (cdr in) prev (+ 1 out))
          (cons (list prev out) (compress in)))))

    (if (null? liste)
      '()
      (helper (cdr liste) (car liste) 1))
      )

这是尾递归版本：

(define (compress liste)

  (define (helper-1 in out)
    (if (null? in)
      '()
      (helper-2 (cdr in) (car in) 1 out)))

  (define (helper-2 in prev count out)
    (if (null? in)
      (append out (list (list prev count)))
      (if (equal? prev (car in))
        (helper-2 (cdr in) prev (+ 1 count) out)
        (helper-1 in (append out (list (list prev count)))))))

  (helper-1 liste '()))
于 2014-03-14T07:13:44.987 回答
1

为简单起见，使用“head-sentinel 技巧”以自上而下的方式构建结果列表：

(define (rle lst)
  (if (null? lst) 
   '()
   (let ((res (list 1)))        ; head sentinel
      (let loop ((p   res)      ; result's last cons cell  
                 (elt (car lst))
                 (cnt 1) 
                 (lst (cdr lst)))
         (if (and (not (null? lst))
                  (equal? elt (car lst)))
            (loop p elt (+ cnt 1) (cdr lst))
            (begin
               (set-cdr! p (list (if (= 1 cnt) elt (list elt cnt))))
               (if (null? lst)
                  (cdr res)     ; skip the head in result, on return
                  (loop (cdr p) (car lst) 1 (cdr lst)))))))))

正如@uselpa 解释的那样，这称为游程编码；为了结果的一致性，我建议(x 1)对非重复元素使用表示。

而错误“错误：应用程序：不是程序；预期程序”，正如其他人所说，意味着系统期望找到一个程序但发现了其他东西，所以不能应用它。Scheme 期望在 list: 中找到一个作为第一个形式的过程(proc args ...)，并尝试将其应用于参数。但是在您的代码中，它不是一个过程，而是一些其他类型的数据。

如果您的方案有左折叠，或者reduce，您可以运行两次 - 首先收集统一的结果，然后在反转时应用您的特殊格式（左折叠的结果通常以相反的顺序构建）：

(define (fold f init lst)            ; if fold is not defined,
   (reduce f init (cons init lst)))  ;   define it in terms of reduce

(define (rle lst)
   (fold (lambda (x acc)             ; NB! MIT-Scheme: (acc x)
             (if (= 1 (cadr x))  (cons (car x) acc)  (cons x acc)))
         '()
      (fold (lambda (x acc)          ; NB! MIT-Scheme: (acc x)
                (if (or (null? acc) (not (equal? (caar acc) x)))
                   (cons (list x 1) acc)
                   (cons (list x (+ (cadar acc) 1)) (cdr acc))))
            '() 
            lst)))
于 2014-03-14T11:37:36.263 回答
1

正如错误消息所说，问题位于“第二个 if 条件的真实谓词”：

((+ counter 1) compressed-cdr)

在这种情况下，(+ counter 1)应该评估为一个过程，但它评估为一个数字。我认为问题在于您不知道如何增加计数器。

你的假谓词有同样的问题：

((cons (car liste) counter) (= counter 0) (compressed-cdr))))))

where(cons (car liste) counter)产生一个列表而不是一个过程。

我认为我们不能真正使用这段代码。我建议看一下R Sahu 的答案，这很接近。或者，我可以向您展示一个尾递归版本，您也可以看看。顺便说一句，这称为运行长度编码，因此我调用了我的程序rle：

(define (rle lst)

  (define (newres prv cnt res)
    (case cnt
      ((0)  res) 
      ((1)  (cons prv res)) 
      (else (cons (list prv cnt) res))))

  (let loop ((lst lst) (prv null) (cnt 0) (res null))
    (if (null? lst)
        (if (zero? cnt)
            (reverse res)
            (loop null null 0 (newres prv cnt res)))
        (let ((c (car lst)))
          (if (eq? c prv)
              (loop (cdr lst) prv (add1 cnt) res)
              (loop (cdr lst) c 1 (newres prv cnt res)))))))
于 2014-03-14T10:46:36.740 回答