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

Наконец, я прочитал умный совет Каза, и вот версия, в которой используется этот трюк. Эта версия всегда обрезает список до середины, если его длина нечетна.

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