Вот несколько версий, которые являются концептуально чистыми (без разрушительных операций, даже неявно), но, возможно, слегка непостижимыми. Оба выполняют больше работы, чем любая из явных (неявно) деструктивных версий. Оба предпринимают некоторую попытку не использовать никаких функций, которые имеют непостоянную сложность по времени, кроме функций, которые они определяют сами (так, например, нет вызовов 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, используявычисленная длина, накапливающая разбиение (ведущая часть списка) в обратном направлении;
- реверсирование ведущего чанка с использованием аккумулятора.
Это немного более эффективно: оно эффективно просматривает списокдважды (один раз для вычисления длины, а затем два полушария), но он составляет всего столько же, сколько список, так как он дважды составляет ведущую половину, один раз назадards, а затем один раз, чтобы обратить его.
Обратите внимание, что хвост списка, возвращаемого этой функцией, разделяет структуру с хвостом исходного списка: это не так для первой функции.
(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 '())))