球拍中的冒泡排序函数

Question

我正在尝试创建一个名为冒泡的函数，它接受一个(listof Num)，并在1次冒泡排序后返回列表。以下是我的代码。

(define (check-numbers-size a b)
  (cond
    [(empty? b) (cons a b)]
    [(> a (list-ref b 0)) (append (list-ref b 0) (append a (rest b)))]
    [else (cons a b)]))


(define (bubble L)
  (foldr (lambda (x y) (check-numbers-size x y)) '() L))


(bubble (list 5 2 4 7 1))

当我尝试运行它时，它给出了以下错误

append: expects a list, given 7

但是，我认为b是一个列表，因为我指定了一个空列表作为这个冒泡函数的基础。我做错什么了？谢谢你的帮助。

Answer 1

函数append需要两个列表作为输入。

> (append (list 1 2 3) (list 4 5))
(list 1 2 3 4 5)

函数list-ref从列表中提取一个元素：

> (list-ref (list 10 11 12 13 14) 2)
12

在你的代码中，你有这样的表达式：

(append (list-ref b 0) ...)

这里的问题是(list-rf b 0)返回的是一个元素，而不是一个列表。要从元素和列表构造新列表，需要使用列表构造函数cons。

(cons (list-ref b 0) ...)

请注意，表达式中也有类似的问题

(append a ...)

Answer 2

你说得对，b恰好是这里的一个列表。但是，像a或(list-ref b 0)这样的append的其他论点又如何呢？

如果你在你的函数上加签名，以显示它们接受什么作为参数，以及它们返回什么，就更容易考虑这些事情。您说过bubble接受一个(Listof Num)，并在1次冒泡排序后返回列表。为什么不在代码中写下来呢？

;; bubble : (Listof Num) -> (Listof Num)
;; returns the list after 1 pass of bubble sort
(define (bubble L)
  ...)

您应该对帮助器函数check-numbers-size执行相同的操作。你说过b是一个列表：

;; check-numbers-size : ??? (Listof Num) -> ???

;; check-numbers-size : Num (Listof Num) -> (Listof Num)
(define (check-numbers-size a b)
  ...)

有两个append调用可能是导致问题的原因：

1. (append a (rest b))
2. (append (list-ref b 0) (append a (rest b)))

(1)可以吗？如果a是Num，b是(Listof Num)，则(1)尝试在Num和(Listof Num)上调用append。这是第一个论点，a，这是问题所在，不是b。看起来你想用cons代替。

(2)可以吗？如果b是一个(Listof Num)，那么(list-ref b 0)将是一个Num。因此，看起来(2)正试图在Num和(Listof Num)上调用append。就像(1)一样，第一个参数就是问题所在。再说一次，看起来您打算使用cons。

cons函数具有签名X (Listof X) -> (Listof X)，其中X可以是任何类型，如Num。

;; check-numbers-size : Num (Listof Num) -> (Listof Num)
(define (check-numbers-size a b)
  (cond
    [(empty? b) (cons a b)]
    [(> a (list-ref b 0)) (cons (list-ref b 0) (cons a (rest b)))]
    [else (cons a b)]))