从列表中删除最后一个元素(scheme)

Question

我需要在Scheme中删除列表的最后一个元素。

例如，假设我有一个列表(1 2 3 4)。我需要返回：

(1 2 3)

我的想法：

reverse(list)
car(list)
reverse(list)

在scheme（racket）中是否有一个reverse函数？

- anon

---

事实上，StackOverflow最好的一点就是一旦一个问题被发布，它可以被其他帖子引用和建立。SO是谷歌搜索时排名靠前的网站之一，因此如果将来有人遇到类似的问题，他们可以从这里学习。 :) - corsiKa

要查找Racket是否有反向函数，请使用docs.racket-lang.org进行查找。 - soegaard

(reverse (cdr (reverse '(1 2 3)))) 在 Chez 和 Racket 中运行良好。无论如何，如果您打开解释器（例如在终端中）并键入一个字母，然后按TAB键，您应该可以访问自动完成建议，这是回答此问题的好方法。 - majik

Answer 1

你写的是："reverse, car, reverse"。我认为你的意思是"reverse, cdr, reverse"。这个解决方法没有问题；它与使用标准列表的任何解决方法一样，都是线性的。

代码如下：

;; all-but-last: return the list, not including the last element
;; list? -> list?
(define (all-but-last l) (reverse (cdr (reverse l))))

如果对列表的多次遍历或不必要的另一个列表副本构造感到困扰，您可以通过直接编写该内容来避免它。

鉴于你几乎已经解决了问题，我假设这不是作业。

以下是 racket 的代码示例：

#lang racket

(require rackunit)

;; all-but-last : return the list, except for the last element
;; non-empty-list? -> list?
(define (all-but-last l)
  (cond [(empty? l) (error 'all-but-last "empty list")]
        [(empty? (rest l)) empty]
        [else (cons (first l) (all-but-last (rest l)))]))

(check-equal? (all-but-last '(3 4 5))
              '(3 4))

- John Clements

---

请注意，此解决方案使用了几个 racket-ism：first＆rest，error，check-equal？等。 我假设这是可以的，因为您的问题已标记为“racket”。 - John Clements

Answer 2

虽然有reverse方法，但使用它效率不高。我建议使用以下递归函数。

(define (remove-last lst)
    (if (null? (cdr lst))
        '()
        (cons (car lst) (remove-last (cdr lst)))))

(remove-last '(1 2 3 4)) ; returns '(1 2 3)

if检查是否在列表的最后一个元素。

- Tim

---

实际上，“reverse”和你的函数一样都是O(n)。两种方法都可以。 - C. K. Young

@Chris：它们确实属于相同的复杂度类，但是这个算法应该会快两倍，因为它只需要遍历一次列表。 - Tim

只有在你使用非常狭窄的“遍历”定义时，才能这样说。因为你的函数不是尾递归的，从调用栈中 consing up 可以被视为第二次遍历。 - C. K. Young

@ChrisJester-Young，我不确定Racket是否实现了尾递归模重组，但在这里可以解决问题。 - dfeuer

Answer 3

SRFI 1（在Racket中使用(require srfi/1)激活）有一个drop-right函数：

 (drop-right '(1 2 3 4) 1)   ; => (1 2 3)

- C. K. Young

---

他可能需要为一项作业做这个。 :) - corsiKa

希望我可以在我的作业中使用这个，不会被发现 ;) - Gaʀʀʏ

在此基础上，我认为核心的 Racket 现在已经具备了这个功能，所以不再需要使用 require。 - Meow

Answer 4

我做了比"reverse(list), car(list), reverse(list)"更简单的事情来获取最后一个元素，请看以下代码：

(define (last-one liste)
  (if(null? (cdr liste))
     null
     (cons (car liste) (last-one (cdr liste)))
  )
)

- Piroh

---

(define (last-one liste) (if (null? (cdr liste)) '() (cons (car liste) (last-one (cdr listed))) ) )我认为返回一个空列表而不是 null 更好。因为在我的 Scheme 版本 9 中，我得到了“未绑定变量：null”的错误。 - rebahozkoc

Answer 5

我会写一个递归函数，遍历列表并使用cons将元素连接起来，如果它后面没有元素，则不添加任何内容。

虽然我已经好几年没写Scheme了，但这就是我的建议。

有人可以继续实现它（除非这是作业，否则他们可能不应该！）

- corsiKa

---

-1 每次追加列表都是一个O(n)的操作，这使得你的整个函数变成了O(n²)。这就是当你使用链表时所遇到的情况。 - C. K. Young

不正确。在链表中添加元素到开头是O(1)的。但是在末尾添加元素的时间复杂度为O(n)，取决于被添加的链表的长度。(请记住，Scheme中的链表是单向链表，而不是双向链表。) - C. K. Young

@Chris 不是的。当你遍历列表时，你已经有了对它的最后一个元素的引用（尾递归的美妙之处），所以它不是O(n)，而是O(1)。 - corsiKa

你可能想写一些代码来解释你的方法，因为我读到的是你在每次迭代中都调用了 append。（你可以在每次迭代中使用 cons --- 这是 O(1) 的 --- 但这不叫做 appending。） - C. K. Young

哦，我明白你的意思了。你误解了我的“append”一词的使用，认为它指的是实际的追加函数，而不是追加的纯文本概念。在这种情况下，我承认追加函数会导致函数顺序膨胀的观点是正确的。 :) - corsiKa

Answer 6

寻找另一种方法的人可以查看以下内容：

(define (removing-last xx)
(remove (list-ref xx (- (length xx) 1)) xx))

- Parmida Pourmatin

---

你测试过 (removing-last '(1 2 3 4 2)) 吗？ - mnemenaut

是的，我认为它可以工作，并且输出将是'(1 2 3 4)。 - Parmida Pourmatin

在Scheme和Racket中，remove函数用于移除列表中的元素。建议实际运行代码以确认效果。 - mnemenaut

强烈推荐学习Scheme/Racket的人参加这个免费的课程。 - mnemenaut

Answer 7

我会编写一个简单的递归，将典型的“empty？mylist”基本情况改为“empty？（rest mylist）”，以便在输入列表仅有1个元素时返回空。

(define (removelast mylist)
  (cond
    [(empty? (rest mylist)) empty]
    [(cons? mylist) (cons (first mylist) (removelast (rest mylist)))]))

(removelast (list 1 2 3 4 5))

顺便提一下，这段代码是在Racket/PLT Scheme中编写的，它是Scheme的一个子集。

- Adrienne