LISP เขียนฟังก์ชันที่เรียกว่า cut-in-half ซึ่งรับรายการและสร้างรายการใหม่ที่มีองค์ประกอบเป็นครึ่งแรกและครึ่งหลัง

ดูว่าคุณสามารถสร้างการบ้านตามแนวคิดนี้ได้หรือไม่:

[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)

นี่คือสิ่งที่ฉันเคยทำในอดีตในการใช้การเรียงลำดับแบบไบนารี่ผสาน (สำหรับการตัดรายการลงครึ่งหนึ่ง การเรียงลำดับทั้งสองครึ่งแบบวนซ้ำ การรวม) โดยพื้นฐานแล้วเรามีเคอร์เซอร์สองตัวที่วิ่งผ่านรายการ หนึ่งก้าวในเวลาสองเท่า โดยกดปุ่มจุดสิ้นสุดของรายการเร็วขึ้นสองเท่า (โดยใช้ cddr ขั้นตอน แทนที่จะเป็น cdr) ซึ่งจะทำให้เคอร์เซอร์อีกตัวอยู่ตรงกลาง

โปรดทราบว่าใน loop ไวยากรณ์ for x on l จะเหมือนกับการทำ for x = l then (cdr l) โดยคร่าวๆ บวกกับการทดสอบการยกเลิกเพื่อสิ้นสุดลูปเมื่อ x กลายเป็นโมฆะ เราสามารถทำได้อย่างนั้นเนื่องจากเราไม่จำเป็นต้องมีการทดสอบการยกเลิกใน x เช่น.

[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)

ซึ่งเป็นสิ่งที่ดีเนื่องจากส่วนคำสั่ง x และ y มีรูปแบบเดียวกัน และความเปรียบต่างระหว่าง cdr และ cddr ก็ชัดเจน

หากต้องการส่งคืนรายการของทั้งสองรายการ ให้ใช้ list แทน values เนื่องจาก Common Lisp มีหลายค่า จึงเป็นสำนวนที่จะใช้ประโยชน์จากค่านั้น แทนที่จะจัดสรรเซลล์รายการเพิ่มเติม

ต่อไปนี้เป็นเวอร์ชันสองสามเวอร์ชันที่มีแนวคิดสะอาด (ไม่มีการดำเนินการทำลายล้าง แม้จะโดยปริยายก็ตาม) แต่อาจเข้าใจไม่ได้เล็กน้อย ทั้งสองทำงานได้มากกว่าเวอร์ชันทำลายล้างที่ชัดเจน (โดยปริยาย) ทั้งสองพยายามที่จะใช้ฟังก์ชันใดที่มีความซับซ้อนของเวลาที่ไม่คงที่ นอกเหนือจากฟังก์ชันที่พวกเขากำหนดไว้เอง (เช่น ไม่มีการเรียกไปยัง reverse หรือ length) ทั้งสองแสดงการวนซ้ำเป็นการเรียกซ้ำส่วนท้าย

จุดประสงค์ของทั้งสองสิ่งนี้คือการดูว่าคุณสามารถสร้างสิ่งต่าง ๆ โดยใช้การดำเนินการที่ค่อนข้างดั้งเดิมเท่านั้นและไม่ใช้การดำเนินการแบบทำลายล้าง และไม่มีการใช้โครงสร้างการวนซ้ำที่ชัดเจน แต่สิ่งนี้มีแนวโน้มที่จะทำให้คุณเสียค่าใช้จ่ายและเวลาเพิ่มขึ้นอีกเล็กน้อย

สำหรับฉัน จุดประสงค์ก็คือเพื่อแสดงให้เห็นว่าปัญหารูปแบบที่ 'สะอาด' เหล่านี้มักจะเข้าใจได้ยากกว่ารูปแบบที่ 'สกปรก' มาก อย่างไรก็ตาม นี่คือความเห็น

ทั้งสองคืนค่าสองครึ่งหนึ่งของรายการเป็นค่าหลายค่า ทั้งสองอาจไม่เหมาะเป็นคำตอบการบ้าน

เวอร์ชันแรกทำงานโดย:

• เดินไปตามรายการโดยคำนวณความยาวและสร้างสำเนากลับรายการ
• เดินลงไปที่สำเนาที่กลับด้านนั้นสะสมไว้เป็นสำเนาที่กลับรายการอีกสองชุดซึ่งเป็นผลลัพธ์

เวอร์ชันนี้จะดำเนินรายการอย่างมีประสิทธิภาพสองครั้ง และสร้างสำเนาที่กลับรายการโดยสมบูรณ์ จากนั้นจึงสร้างสำเนา นั้น ที่กลับรายการทั้งหมด

(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 '())))

เวอร์ชันที่สองทำงานโดย:

• เดินไปตามรายการเพื่อคำนวณความยาวของรายการ
• การแยกรายการออกเป็น halg โดยใช้ความยาวที่คำนวณได้ โดยสะสมการแยก (ส่วนนำของรายการ) ไปข้างหลัง
• การกลับก้อนนำโดยใช้ตัวสะสม

วิธีนี้จะมีประสิทธิภาพมากกว่าเล็กน้อย: โดยจะเดินไปตามรายการสองครั้งอย่างมีประสิทธิภาพ (หนึ่งครั้งเพื่อคำนวณความยาว จากนั้นจึงเดินครึ่งทางสองครั้ง) แต่จะถือว่ามากเท่ากับรายการเท่านั้น เนื่องจากจะถือว่าครึ่งนำสองครั้ง ถอยหลังหนึ่งครั้งแล้วหนึ่งครั้ง เพื่อย้อนกลับ

โปรดทราบว่าส่วนท้ายของรายการที่ส่งคืนโดยฟังก์ชันนี้จะแชร์โครงสร้างร่วมกับส่วนท้ายของรายการเดิม ซึ่งไม่เป็นความจริงสำหรับฟังก์ชันแรก

(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)))

ในที่สุด ฉันได้อ่านคำใบ้อันชาญฉลาดของ Kaz แล้ว และนี่คือเวอร์ชันที่ใช้เคล็ดลับนั้น เวอร์ชันนี้จะตัดรายการก่อนจุดกึ่งกลางเสมอหากความยาวของรายการเป็นเลขคี่

(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 '())))