scheme - Insert-everywhere 程序

Question

我正在尝试编写一个过程，它接受一个符号和一个列表，并将符号插入给定列表内的每个可能位置(从而生成一个列表列表)。我编写了以下必须实现的定义:

1

(define (insert-at pos elmt lst)
 (if (empty? lst) (list elmt)
 (if (= 1 pos)
  (cons elmt lst)
  (cons (first lst) 
        (insert-at (- pos 1) elmt (rest lst))))))

2

(define (generate-all-pos start end)
 (if (= start end)
  (list end)
  (cons start (generate-all-pos (+ start 1) end))))

1 在列表(数字)、符号和列表本身中占据一个位置，并将符号插入到请求的位置。2 采用开始和目标位置(数字)并创建一个排序列表，其中包含从开始到目标的数字。到目前为止，我得到了这个:

(define (insert-everywhere sym los)
 (cond
  [(empty? los) (list sym)]
   [else (cons (insert-at (first (generate-all-pos (first los)
    (first (foldl cons empty los)))) sym los) (insert-everywhere sym (rest los)))
           ]
         )
       )

结果

> (insert-everywhere 'r '(1 2 3))
(list (list 'r 1 2 3) (list 2 'r 3) (list 3 'r) 'r)

所以我实际上设法移动了“r”。我对保留列表的前面成员感到困惑。也许我遗漏了一些非常简单的东西，但我已经盯着代码看了很长时间，这是我迄今为止得到的最干净的结果。任何帮助将不胜感激。

Answer 1

Óscar López's answer显示了如何根据您已经定义的过程来执行此操作。我想指出一种递归输入列表的方法。它使用一个名为 revappend 的辅助函数(我从 Common Lisp 的 revappend 中取了这个名字)。 revappend 获取列表和尾部，并有效地返回与 (append (reverse list) tail) 相同的内容。

(define (revappend list tail)
  (if (null? list)
      tail
      (revappend (rest list)
                 (list* (first list) tail))))

> (revappend '(3 2 1) '(4 5 6))
'(1 2 3 4 5 6)

我们对这样的函数感兴趣的原因是，当我们递归输入列表时，我们可以构建一个我们已经看到的元素的列表，但它的顺序是相反的。也就是说，当我们沿着 (1 2 3 4 5) 走时，很容易得到:

rhead       tail        (revappend rhead (list* item tail))
----------- ----------- -----------------------------------
         () (1 2 3 4 5) (r 1 2 3 4 5)
        (1) (2 3 4 5)   (1 r 2 3 4 5)
      (2 1) (3 4 5)     (1 2 r 3 4 5)
    (3 2 1) (4 5)       (1 2 3 r 4 5)
  (4 3 2 1) (5)         (1 2 3 4 r 5)
(5 4 3 2 1) ()          (1 2 3 4 5 r)

在每种情况下，(revappend rhead (list* item tail)) 返回一个列表，其中一个位置插入了 item。因此，如果我们建立results 列表以相反的顺序排列，并在循环结束时将其reverse。

(define (insert-everywhere item list)
  (let ie ((tail list)
           (rhead '())
           (results '()))
    (if (null? tail)
        (reverse (list* (revappend rhead (list* item tail)) results))
        (ie (rest tail)
            (list* (first tail) rhead)
            (list* (revappend rhead (list* item tail)) results))))) 

(insert-everywhere 'r '(1 2 3))
;=> '((r 1 2 3) (1 r 2 3) (1 2 r 3) (1 2 3 r))

有趣的是子列表都共享相同的尾部结构。也就是说，子列表共享如下“图表”所示的结构。

;=> '((r 1 2 3) (1 r 2 3) (1 2 r 3) (1 2 3 r))
;        -----       +++         o   
;          +++         o
;            o