Jawaban singkatnya: versi pertama reverse salah membuat daftar yang tidak tepat, versi kedua tidak efisien membuat daftar yang tepat. Kita bisa melakukan lebih baik selama kita memahami perbedaan antara append dan cons.
append menggabungkan dua daftar. Jika kita menggunakannya hanya untuk menambahkan elemen di akhir satu daftar, kita akan melakukan lebih banyak pekerjaan daripada yang dibutuhkan: kita harus melintasi seluruh daftar setiap kali hanya untuk meletakkan satu elemen terakhir (lihat: Algoritma Schlemiel the Painter). Oleh karena itu, implementasi reverse yang menggunakan append dapat memiliki kompleksitas yang sama buruknya dengan O(n^2).
Di sisi lain, cons menambahkan satu elemen ke bagian atas daftar, untuk kompleksitas O(n) dalam implementasi reverse. Secara umum, dalam Skema Anda harus mencoba menghindari penggunaan append untuk membuat daftar keluaran baru, selalu pilih cons. Sekarang mari kita lihat apa yang dikembalikan oleh algoritme Anda menggunakan cons:
(reverse '(1 2 3 4 5))
=> '(((((() . 5) . 4) . 3) . 2) . 1)
Mengapa demikian? karena untuk membuat daftar yang tepat dengan cons argumen kedua harus berupa daftar lain yang tepat, tetapi Anda meneruskan satu elemen. Implementasi yang benar memerlukan parameter akumulator - dan kebetulan, ini lebih efisien, karena menggunakan rekursi ekor, sebuah konsep yang seharusnya sudah Anda pahami, seperti yang diperkenalkan di bagian 1.2 buku ini. Coba ini:
(define (reverse lst acc)
(if (null? lst)
acc
(reverse (cdr lst) (cons (car lst) acc))))
(reverse '(1 2 3 4 5) '())
=> '(5 4 3 2 1)
Untuk bagian terakhir dari pertanyaan: daftar ditampilkan dengan mcons (m berarti sel cons dapat diubah) karena bahasa yang Anda gunakan, coba beralih ke #lang racket, yang menggunakan < em>tidak dapat diubah cons secara default, dan akan dicetak seperti yang Anda harapkan.
person
Óscar López
schedule
17.01.2015
