Хвост рекурсивного решения
(defun split (n l &optional (acc-l '()))
(cond ((null l) (list (reverse acc-l) ()))
((>= 0 n) (list (reverse acc-l) l))
(t (split (1- n) (cdr l) (cons (car l) acc-l)))))
Улучшенная версия
(в этой версии гарантируется, что acc-l находится наначало '()):
(defun split (n l)
(labels ((inner-split (n l &optional (acc-l '()))
(cond ((null l) (list (reverse acc-l) ()))
((= 0 n) (list (reverse acc-l) l))
(t (inner-split (1- n) (cdr l) (cons (car l) acc-l))))))
(inner-split n l)))
Проверьте это:
(split 3 '(1 2 3 4 5 6 7))
;; returns: ((1 2 3) (4 5 6 7))
(split 0 '(1 2 3 4 5 6 7))
;; returns: (NIL (1 2 3 4 5 6 7))
(split 7 '(1 2 3 4 5 6 7))
;; returns ((1 2 3 4 5 6 7) NIL)
(split 9 '(1 2 3 4 5 6 7))
;; returns ((1 2 3 4 5 6 7) NIL)
(split -3 '(1 2 3 4 5 6 7))
;; returns (NIL (1 2 3 4 5 6 7))
В улучшенной версии рекурсивная функция размещена на один уровень глубже (вид инкапсуляции ) с помощью labels (вид let, который позволяет определять локальные функции, но таким образом, что им разрешено вызывать себя - так что это позволяет рекурсивные локальные функции).
Как я пришелк решению:
Каким-то образом ясно, что первый список в результате должен быть результатом последовательного следования одного элемента за другим с начала l.Однако consing добавляет элемент к существующему списку в его начале, а не в конце.Итак, последовательная сдача машины в список приведет к обратному порядку.Таким образом, ясно, что на последнем этапе, когда возвращается первый список, он должен быть reverse d.Второй список - это просто (cdr l) последнего шага, поэтому его можно добавить к результату на последнем шаге, когда результат будет возвращен.
Итак, я подумал, что хорошо бы накопить первый список в (acc-l) - аккумулятор в основном является последним элементом в списке аргументов хвостовых рекурсивных функций, компонентами первого списка.Я назвал это acc-l - список-аккумуляторов.
При написании рекурсивной функции, часть cond начинается с тривиальных случаев.Если входными данными являются число и список, наиболее тривиальные случаи - и последние шаги рекурсии - это случаи, когда
- список пуст
(equal l '()) ---> (null l) - и число равно нулю ---->
(= n 0) - на самом деле (zerop n).Но позже я изменил его на (>= n 0), чтобы отлавливать также случаи, когда в качестве входных данных приводится отрицательное число.
(Таким образом, очень часто рекурсивные cond части имеют null или zerop вих условия.)
Когда список l пуст, тогда два списка должны быть возвращены - тогда как второй список является пустым списком, а первый список - неинтуитивно - reverse d acc-l.Вы должны построить их с (list ), так как аргументы list вычисляются незадолго до возврата (в отличие от quote = '(...), где результат не может быть оценен как sth на последнем шаге.)
Когда n равно нулю (и позже: когда n отрицательно), тогда ничего не нужно делать, кроме как вернуть l в качестве второго списка и то, что было накоплено для первого списка до сих пор - но в обратном порядке.
Во всех остальных случаях (t ...), машина списка l cons отправляется в список, который был накоплен до сих пор (для первого списка): (cons (car l) acc-l), и это я даю в качестве списка аккумулятора (* 1071)*) до split и остальной список как новый список в этом вызове (cdr l) и (1- n).Это уменьшение в рекурсивном вызове очень типично для определений рекурсивных функций.
Тем самым мы рассмотрели все возможности для одного шага в рекурсии.И это делает рекурсию такой мощной: покорите все возможности в ОДНОМ шаге - и тогда вы определили, как обрабатывать почти бесконечное число случаев.
Нерекурсивное решение (по вдохновению Дэна РобертсонаРешение - Спасибо, Дэн! Особенно его решение с destructuring-bind мне понравилось.
(defun split (n l)
(cond ((null l) (list '() '()))
((>= 0 n) (list '() l))
(t (destructuring-bind (left right) (split (1- n) (cdr l))
(list (cons (car l) left) right)))))
И решение только с очень элементарными функциями (только null, list,>=, let, t, cons, car, cdr, cadr)
(defun split (n l)
(cond ((null l) (list '() '()))
((>= 0 n) (list '() l))
(t (let ((res (split (1- n) (cdr l))))
(let ((left-list (car res))
(right-list (cadr res)))
(list (cons (car l) left-list) right-list))))))