创建一个由重复元素组成的列表列表。

Question

这是一个我卡住的作业问题。我需要在Racket中创建一个函数，不使用显式递归或本地函数，该函数接受一组成对列表，其中每个对的第一个元素是非负整数，并生成新的列表，其中每个列表是每个对的第二个元素的k个出现次数，其中k是每个对的第一个元素。例如，（expand-pairs（list（list 1 2）（list 3 4）））将生成（list（list 2）（list 4 4 4））

我已经编写了一些代码，但仅适用于第二个元素为数字的情况。由于问题没有指定第二个元素的类型，因此我假设它需要适用于任何元素。因此，我的函数可以解决上面的示例，但无法解决（expand-pairs（list（list 1'a）（list 3'b）））。

以下是我的代码:

(define (expand-pairs plst) 
  (map 
   (lambda (x) 
     (map 
      (lambda (y) (+ (first (rest x)) y)) 
      (build-list (first x) (lambda (z) (- z z)))))
   plst))

我的主要问题是我不知道如何创建一个长度为k的列表，而不使用递归或build-list，但是如果我使用build-list，它会创建一个数字列表，我不知道如何将其转换为符号或其他元素的列表。

有谁能指点一下我正确的方向吗？

- user2828706

---

这是一种游程长度编码形式。除了在这里获得的答案，您可能会发现Rosetta Code中关于运行长度编码的代码示例很有启发性（其中包括各种Lisp（Clojure，Common Lisp和Scheme）的代码）。那里的任务是压缩和解压缩_字符串_（而不是列表），但其中一些技术仍然可能有所帮助。 - Joshua Taylor

此外，关于“pair”一词的说明。在Scheme中，“pair”通常指cons的返回值，即一个点对，一个cons单元。这与两个元素的列表不同，因为(1 2) == (1 . (2 . ()))需要两个cons单元。我之所以指出这一点，是因为基于函数“接受一对列表”的规范，使用案例(expand-pairs (list (list 1 2) (list 3 4)))有些令人惊讶。它可以是(expand-pairs (list (cons 1 2) (cons 3 4))) == (expand-pairs '((1 . 2) (3 . 4)))。 - Joshua Taylor

Answer 1

下面是另一种可能的实现方法，基于 @RomanPekar 的答案，但更符合 Racket 的惯用语法：

(define (expand-pairs lst)
  (map (lambda (s)
         (build-list (first s) (const (second s))))
       lst))

它利用高阶过程map、const和build-list来创建一个不使用显式递归或local的实现。这里的诀窍是要理解以下表达式如何返回x的5个副本：

(build-list 5 (const  'x))
            ^    ^     ^
      #copies constant element

=> '(x x x x x)

- Óscar López

---

我并不是Racket专家，但看起来在这里使用const确实更符合Racket的风格，所以+1。 - Roman Pekar

Answer 2

像这样的东西：

(define (expand-pairs plst)
  (map (lambda(x) (build-list (car x) (lambda(k) (cadr x)))) plst))

你不必在 build-list 中使用 k，只需取出一对的第二个元素。

- Roman Pekar