LISP Tulis fungsi yang disebut cut-in-half yang menerima daftar dan membuat daftar baru yang elemennya adalah paruh pertama dan kedua

Lihat apakah Anda dapat membuat pekerjaan rumah berdasarkan ide ini:

[1]> (loop with l = '(1 2 3 4 5 6 7)
           for x on l
           for y = x then (cddr y)
           when (null y)
            return (values (ldiff l x) x))
(1 2 3 4) ;
(5 6 7)

[2]> (loop with l = '(1 2 3 4 5 6 7 8)
           for x on l
           for y = x then (cddr y)
           when (null y)
            return (values (ldiff l x) x))
(1 2 3 4) ;
(5 6 7 8)

Ini adalah hal yang pernah saya lakukan di masa lalu dengan mengimplementasikan pengurutan penggabungan biner (untuk memotong daftar menjadi dua, mengurutkan dua bagian secara rekursif, penggabungan). Pada dasarnya kita memiliki dua kursor yang menelusuri daftar; satu langkah dalam waktu ganda, mencapai akhir daftar dua kali lebih cepat (menggunakan cddr langkah daripada cdr), sehingga kursor lainnya berada di tengah.

Perhatikan bahwa di loop, sintaks for x on l kira-kira sama dengan melakukan for x = l then (cdr l), ditambah tes terminasi untuk mengakhiri perulangan ketika x menjadi nol. Kita dapat melakukannya dengan cara itu karena kita tidak memerlukan tes terminasi pada x. Yaitu.

[9]> (loop with l = '(1 2 3 4 5 6 7 8)
           for x = l then (cdr x)
           for y = x then (cddr y)
           when (null y)
            return (values (ldiff l x) x))
(1 2 3 4) ;
(5 6 7 8)

Hal ini bagus karena klausa x dan y mengikuti bentuk yang sama, dan kontras antara cdr dan cddr dibuat eksplisit.

Untuk mengembalikan daftar dari dua daftar, gunakan list alih-alih values. Karena Common Lisp memiliki banyak nilai, adalah idiomatis untuk memanfaatkannya daripada mengalokasikan sel daftar tambahan.

Berikut adalah beberapa versi yang secara konseptual bersih (tidak ada operasi destruktif, bahkan secara implisit), namun mungkin agak sulit dipahami. Keduanya melakukan lebih banyak pekerjaan daripada versi destruktif yang jelas (secara implisit). Keduanya berusaha untuk tidak menggunakan fungsi yang memiliki kompleksitas waktu tidak konstan selain fungsi yang mereka definisikan sendiri (jadi, misalnya, tidak ada panggilan ke reverse atau length). Keduanya menyatakan iterasi sebagai rekursi ekor.

Tujuan dari kedua hal ini adalah untuk melihat bagaimana Anda dapat membangun sesuatu hanya dengan menggunakan operasi yang cukup primitif dan tidak menggunakan operasi destruktif, dan tidak menggunakan konstruksi iterasi yang eksplisit tetapi hal ini cenderung menghabiskan lebih banyak waktu dan biaya.

Bagi saya, tujuannya juga untuk menunjukkan bahwa varian masalah yang 'bersih' ini sering kali lebih sulit dipahami dibandingkan varian masalah yang 'kotor'. Namun ini hanyalah opini.

Keduanya mengembalikan dua bagian daftar sebagai beberapa nilai. Mungkin keduanya tidak cocok sebagai jawaban pekerjaan rumah.

Versi pertama bekerja dengan:

• menelusuri daftar dengan menghitung panjangnya dan membuat salinan terbalik;
• menelusuri salinan terbalik itu dan mengumpulkannya menjadi salah satu dari dua salinan terbalik selanjutnya yang merupakan hasilnya.

Versi ini secara efektif menjalankan daftar dua kali dan membuat salinan terbalik lengkap dan kemudian salinan terbalik lengkap dari itu.

(defun halfify (list)
  ;; Return two values: a copy of the first half of LIST and a copy of
  ;; the second half of LIST.  'half' is defined as by (round (length
  ;; list) 2).
  ;;
  ;; This works by walking down the list to accumulate a reversed copy
  ;; of it and its length: half/accum does this.  When this is done,
  ;; rev/split then walks down the reversed copy accumulating a
  ;; further reversed copy into one of two accumulators.
  ;;
  ;; This walks the list twice, and conses essentially two copies of
  ;; it.
  (labels ((half/accum (tail n accum)
             (if (null tail)
                 (rev/split accum (round n 2) '() '())
               (half/accum (rest tail) (1+ n) (cons (first tail) accum))))
           (rev/split (tail n h1 h2)
             (cond ((null tail)
                    (values h1 h2))
                   ((> n 0)
                    (rev/split (rest tail) (1- n) (cons (first tail) h1) h2))
                   (t
                    (rev/split (rest tail) n h1 (cons (first tail) h2))))))
    (half/accum list 0 '())))

Versi kedua bekerja dengan:

• menelusuri daftar untuk menghitung panjangnya;
• membagi daftar dalam halg menggunakan panjang yang dihitung, mengumpulkan pembagian (bagian utama daftar) ke belakang;
• membalikkan potongan utama menggunakan akumulator.

Ini sedikit lebih efisien: ini secara efektif menelusuri daftar dua kali (sekali untuk menghitung panjang, dan kemudian dua setengah jalan), tetapi ini hanya menghabiskan sebanyak yang ada dalam daftar, karena ini menghabiskan setengah bagian depan dua kali, sekali ke belakang dan kemudian sekali untuk membalikkannya.

Perhatikan bahwa ekor daftar yang dikembalikan oleh fungsi ini memiliki struktur yang sama dengan ekor daftar asli: itu tidak berlaku untuk fungsi pertama.

(defun halfify (list)
  ;; Return two values: a copy of the first half (rounded) of the
  ;; list, and the remainder of it.  
  ;;
  ;; This does essentially two walks down the list (once to compute
  ;; the length, half to build a reversed of the first half and then
  ;; half again to reverse it, and conses as much as the whole list
  ;; (half for the reversed half-copy, half to reverse it).  I don't
  ;; think you can do better than this without code which is
  ;; implicitly destructive, or not tail-recursive.
  (labels ((half (tail n)
             (if (null tail)
                 (split list (round n 2) '())
               (half (rest tail) (1+ n))))
           (split (tail m results)
             (if (zerop m)
                 (values (rev results '()) tail)
               (split (rest tail) (1- m) (cons (first tail) results))))
           (rev (tail result)
             (if (null tail)
                 result
               (rev (rest tail) (cons (first tail) result)))))
    (half list 0)))

Akhirnya, saya telah membaca petunjuk cerdas Kaz, dan inilah versi yang menggunakan trik tersebut. Versi ini akan selalu memotong daftar sebelum titik tengahnya jika panjangnya ganjil.

(defun halfify (list)
  (labels ((half/step (fast slow a)
             (if (null fast)
                (values (rev a '()) slow)
               (let ((fast-tail (rest fast)))
                 (if (null fast-tail)
                     (values (rev a '()) slow)
                   (half/step (rest fast-tail) (rest slow)
                              (cons (first slow) a))))))
           (rev (tail result)
             (if (null tail)
                 result
               (rev (rest tail) (cons (first tail) result)))))
    (half/step list list '())))