Критик мой Lisp, пожалуйста

Я создал небольшую рутину:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (let ((oddresult '())
    (evenresult '()))
    (loop for n from 0 to (- (length seq) 1) do
      (if (oddp n)
          (push (nth n seq) oddresult)
        (push (nth n seq) evenresult)))
    (list (reverse oddresult) (reverse evenresult))))

И использовать его:

CL-USER> (unzip '(1 2 3 4 5 6))
((2 4 6) (1 3 5))

Однако я остро осознаю свою способность ~~писать~~ botch С++ на любом языке и хотел бы получить некоторый анализ моего unzip для хорошего общего стиля Lisp.

Ответ 1

Прежде всего обратите внимание, что '() и () эквивалентны, так как пустой список самооценивается и равен NIL, и в любом случае вам не нужны те, которые находятся в LET, потому что NIL подразумевается синтаксисом `(let (variable)...), который является причиной того, что вам нужно скобки вокруг каждой привязки при задании начального значения.

Не нужно использовать LET для этого случая. С помощью LOOP функции более подробно эта функция может быть записана как:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (loop for n from 0
        for element in seq
        if (oddp n)
          collect element into oddresult
        else
          collect element into evenresult
        finally (return (list oddresult evenresult))))

Лично я предпочитаю iterate для большей итерации, используя которую он может быть записан как:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (iter (for element in seq)
        (for n from 0)
        (if (oddp n)
            (collect element into oddresult)
            (collect element into evenresult))
        (finally (return (list oddresult evenresult)))))

или даже:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (iter (generate element in seq)
        (collect (next element) into evenresult)
        (collect (next element) into oddresult)
        (finally (return (list oddresult evenresult)))))

EDIT: Дополнительные примечания: Имя unzip условно обозначает немного другую функцию. Имя аргумента должно быть действительно list, так как seq предполагает, что функция также принимает векторы. Хотя возможно функционирование функций, основанных на обобщенных последовательностях, обычно не рекомендуется, поскольку списки и векторы имеют разные характеристики производительности. В частности, произвольный доступ через NTH является линейным временем для списков, что означает, что вы почти никогда не будете его использовать. Даже если временная стоимость невелика, она обычно указывает, что вы должны использовать другую структуру данных.

Ответ 2

Функция (nth n list) должна пересекать список, чтобы получить доступ к n-му элементу, операции O (n), и он вызвал O (n) раз в вашей реализации, делая весь процесс O (n ^ 2). Вы можете сделать то же самое в O (n):

(defun unzip (list)
  (loop for (x y) on list by #'cddr
        collect x into a
        collect y into b
        finally (return (list a b))))

Ответ 3

Посмотрите на свой код:

(defun unzip (seq)
  "Takes an even-length list and breaks it apart by evens/odd index"

 ; you name the variable seq (sequence), but the documentation mentions
 ; only lists. Sequence is in CL an abstraction over lists and vectors. 

 ; also nothing in the code really says that the list needs to be even-length  

  (let ((oddresult  '())
        (evenresult '()))
    (loop for n from 0 to (- (length seq) 1) do  ; you can iterate BELOW         
      (if (oddp n)
          (push (nth n seq) oddresult)    ; <- NTH is inefficient for lists
        (push (nth n seq) evenresult)))   ; <- NTH is inefficient for lists
    (list (reverse oddresult)             ; <- return multiple values
          (reverse evenresult))))

Вот версия для списков:

(defun unzip (list &aux oddresult evenresult (odd t))
  "Takes a list and breaks it apart by evens/odd index"
  (dolist (element list (values (reverse oddresult) (reverse evenresult)))
    (if (setf odd (not odd))
        (push element oddresult)
      (push element evenresult))))

Пример (обратите внимание, что индексирование равно нулю на основе CL, я изменил этот пример, чтобы сделать его менее запутанным):

CL-USER 10 > (unzip '(0 1 2 3 4 5))
(1 3 5)
(0 2 4)

Вот версия, которая ожидает список четной длины и использует LOOP:

(defun unzip (list)
  "Takes an even-length list and breaks it apart by evens/odd index"
  (loop for (even odd) on list by #'cddr
        collect even into evenresult
        collect odd  into oddresult
        finally (return (values oddresult evenresult))))

Ответ 4

Единственное, что я вижу, - это nth. Вы должны перебирать список вместо этого, поскольку nth, скорее всего, придется перебирать список в любом случае. Забудьте о массивах и индексировании массива:)

К сожалению, я не знаю, как это сделать в Lisp, но в Scheme вы просто используете имя let.

Ответ 5

Я бы решил это либо с LOOP, либо с рекурсивной функцией.

Для решения на основе LOOP @Ramarren в значительной степени прибил его.

Если не важно знать, что произошло от даже индексов и что произошло от нечетного, я бы использовал что-то вроде:

(defun unzip (list &optional acc1 acc2)
   (if seq
       (unzip (cdr list) acc2 (cons (car list) acc1)))
       (list (nreverse acc1) (nreverse acc2))))

Если вам необходимо знать, что произошло от нечетных или даже индексов, я бы обернул этот UNZIP в вспомогательную функцию, которая сравнивает CAR списка и CAAR возвращаемого значения. Если они совпадают, отдайте их обратно, в противном случае замените два списка в списке результатов.

Ответ 6

Рекурсивное решение:

(defun unzip (seq &optional oddresult evenresult)
  (if (null seq)
      (list (reverse oddresult) (reverse evenresult))
    (if (oddp (car seq))
        (unzip (cdr seq) (cons (car seq) oddresult) evenresult)
      (unzip (cdr seq) oddresult (cons (car seq) evenresult)))))

Ответ 7

Вместо того, чтобы перебирать элементы списка, вы должны использовать for-each или car и cdr для перебора списка до тех пор, пока он не будет пуст.
Я бы не назвал его unzip, потому что это не противоположность zip.

Изменить: Чтобы быть более конкретным, я ожидаю, что zip возьмет пару списков и вернет список пар, поэтому unzip должен взять список пар и вернуть пару списков. Я ожидаю, что это будет выглядеть следующим образом:

(defun unzip (list)
  (let ((a '())
        (b '()))
    (for-each (lambda (i) (push (first i) a) (push (second i) b)) list)
    (values (nreverse a) (nreverse b))))

Ответ 8

Версия схемы, только для целевой практики.:-) (Требуется функция SRFI 1 fold.)

(define (unzip l)
  (define (iter e v)
    (list (not (car v)) (caddr v) (cons e (cadr v))))
  (define (swap-if p a b)
    (if p (list b a) (list a b)))
  (map reverse
       (apply swap-if (fold iter '(#t () ()) l))))

Чтобы изменить порядок возвращаемых списков (т.е. даже индексированные элементы), просто измените #t на #f.

Ответ 9

Вот еще одно возможное решение, использующее рекурсию:

(defun unzip (l)
  (labels ((every-other (l) (if l (cons (car l) (every-other (cddr l))))))
    (list (every-other (cdr l)) (every-other l))))

Сначала мы определяем вспомогательную функцию, которая принимает все остальные элементы из списка. Затем мы запускаем эту функцию в исходном списке с пропущенным первым элементом и в исходном списке.

Недостаток: из-за рекурсии он может переполнять поток для больших списков. Если он должен обрабатывать большие списки, см. @Vatine для хвостового рекурсивного решения.

Ответ 10

Вот версия цикла, которая не чувствительна к входам с нечетной длиной, это лишь незначительная вариация ответа @huaiyuan с добавленным предложением when:

(defun unzip (list)
  (loop for (x y) on list by #'cddr
     collect x into a
     when y
     collect y into b
     finally (return (list a b))))