时间戳

首页 > 解决方案 > 从列表末尾开始在另一个单词旁边插入单词

scheme - 从列表末尾开始在另一个单词旁边插入单词

问题描述

我有在所选单词右侧插入新单词的代码

(define insertR
  (lambda (new old lst)
    (cond
      ((null? lst) (lst))
      (else (cond
              ((eq? (car lst) old)
               (cons old
                     (cons new (cdr lst))))
              (else (cons (car lst)
                          (insertR new old
                                   (cdr lst)))))))))

我需要让它从列表末尾开始在单词的第一次出现旁边插入该单词。尝试使用反向但无法使其正常工作。

标签： schemeracket

解决方案

您可以采取两种策略将其添加到最后一次出现的旁边。

第一种是使用助手并从反向列表开始。这非常简单，也是我的首选解决方案。 

(define (insert-by-last-match insert find lst)
  (let loop ((lst (reverse lst)) (acc '()))
    (if (null? lst) 
        acc
        (let ((a (car lst)))
          (if (equal? a find)
              (append (reverse (cdr lst))
                      (list* find insert acc))
              (loop (cdr lst) (cons a acc)))))))

另一个有点晦涩难懂。每当您找到用回调替换的元素时last-match，该回调将替换计算，直到它被替换和列表的其余部分调用，这当然是正确的结果。直到列表末尾完成的工作被简单地丢弃，因为它没有被使用，但是我们这样做是因为我们不确定是否要找到以后的工作，然后所有的工作直到当然包含在结果中.

(define (insert-by-last-match insert find lst)
  (define (helper lst last-match)
    (if (null? lst) 
        (last-match)        
        (let* ((a (car lst)) (d (cdr lst)))
          (cons a
                (if (equal? a find)
                    (let/cc k
                      (helper d (lambda () (k (cons insert d)))))
                    (helper d last-match))))))

  (helper lst (lambda () lst)))

call/cc（或其变体let/cc）通常被描述为时间旅行或高级 goto。这不是很直观。这是一个 CPS 版本：

(define (insert-by-last-match insert find lst)
  (define (helper lst last-match k)
    (if (null? lst) 
        (last-match)        
        (let* ((a (car lst)) (d (cdr lst)) (k2 (lambda (v) (k (cons a v)))))
          (if (equal? a find)
              (helper d (lambda () (k2 (cons insert d))) k2)
              (helper d last-match k2)))))
  (helper lst (lambda () lst) (lambda (v) v)))

基本上，这与之前的相同，只是在这里我编写了 CPS 代码，并使用let/cc实现为我完成的版本，并且我可以k在我需要的地方使用它。在这个版本中，您会看到没有魔法或时间旅行，但稍后应该发生的执行只是在某个时间点被替换。

推荐阅读