方案运行长度编码

Question

问题是：

编写一个函数(encode L)，它接受一个原子列表L，运行长度对该列表进行编码，使得输出是一个形式为[=15的对列表=] 其中第一个元素是一个值，第二个是该值在被编码列表中出现的次数。

例如：

(encode '(1 1 2 4 4 8 8 8)) ---> '((1 2) (2 1) (4 2) (8 3))

这是我目前的代码：

(define (encode lst)
  (cond 
    ((null? lst) '())
    (else ((append (list (car lst) (count lst 1)) 
                   (encode (cdr lst)))))))

(define (count lst n)
  (cond 
    ((null? lst) n)
    ((equal? (car lst) (car (cdr lst))) 
      (count (cdr lst) (+ n 1)))
    (else (n)))))

所以我知道这行不通，因为我真的想不出一种方法来有效地计算列表中特定原子的数量，因为我会迭代列表。此外，在继续计算列表中的下一个唯一原子之前，保存前一个 (value length) 对。基本上，我的主要问题是想出一种方法来计算我在列表中看到的原子数量，以创建我的 (value length) 对。

Answer 1

您需要一个将计数作为附加参数的辅助函数。您相互检查前两个元素，如果匹配则通过增加其余元素的计数来递归，或者通过匹配并在递归调用中将计数重置为 1 来递归。

这是您需要实现 <??> 部分的草图：

(define (encode lst)
  (define (helper lst count)
    (cond ((null? lst) <??>)
          ((null? (cdr lst)) <??>))
          ((equal? (car lst) (cadr lst)) <??>)
          (else (helper <??> <??>))))
  (helper lst 1))

;; tests
(encode '())              ; ==> ()
(encode '(1))             ; ==> ((1 1))
(encode '(1 1))           ; ==> ((1 2))
(encode '(1 2 2 3 3 3 3)) ; ==> ((1 1) (2 2) (3 4))

使用 命名的 let 表达式

这种使用带有状态变量的递归辅助过程的技术在 Scheme 中非常普遍，以至于有一种特殊的 let 形式可以让您更好地表达模式

(define (encode lst)
  (let helper ((lst lst) (count 1))
    (cond ((null? lst) <??>)
          ((null? (cdr lst)) <??>))
          ((equal? (car lst) (cadr lst)) <??>)
          (else (helper <??> <??>)))))

评论你问题中的代码：它有多余的括号..

((append ....)) 表示调用 (append ....) 然后调用该结果，就好像它是一个函数一样。因为 append 制作的列表会像 ERROR: application: expected a function, got a list.

这样惨败

(n) 表示将 n 作为函数调用。请记住 + 只是一个变量，如 n。函数和 Scheme 中的其他值之间没有区别，当你放置一个像 (if (< v 3) + -) 这样的表达式时，如果你用括号括起来调用它 ((if (< v 3) + -) 5 3); ==> 8 or 2

，它需要计算一个函数

方案运行长度编码

Scheme run length encoding

scheme

functional-programming

run-length-encoding