Лисп: Элегантный способ убрать последние нули из списка? (Обзор) - PullRequest
Новая
       53

Лисп: Элегантный способ убрать последние нули из списка? (Обзор)

4 голосов
/ 10 июля 2009

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

(defun strip-tail (lst)
  (let ((last-item-pos (position-if-not #'null lst :from-end t)))
    (if last-item-pos
      (subseq lst 0 (1+ last-item-pos)))))

; Test cases.
(assert (eq nil (strip-tail nil)))
(assert (eq nil (strip-tail '(nil))))
(assert (equal '(a b) (strip-tail '(a b nil nil))))
(assert (equal '(a nil b) (strip-tail '(a nil b nil))))
(assert (equal '(a b) (strip-tail '(a b))))

Возможно, ясно, но я не уверен. Есть ли более хитрый способ сделать это?

Ответы [ 6 ]

3 голосов
/ 10 июля 2009 
(defun strip-tail (ls)
    (labels ((strip-car (l)
                  (cond ((null l)       nil)
                        ((null (car l)) (strip-car (cdr l)))
                        (t              l))))
        (reverse (strip-car (reverse ls)))))

Пробный прогон (против ваших тестовых случаев): 

[1]> (assert (eq nil (strip-tail nil)))
NIL
[2]> (assert (eq nil (strip-tail '(nil)))) ;'
NIL
[3]> (assert (equal '(a b) (strip-tail '(a b nil nil))))
NIL
[4]> (assert (equal '(a nil b) (strip-tail '(a nil b nil))))
NIL
[5]> (assert (equal '(a b) (strip-tail '(a b))))
NIL
[6]>
3 голосов
/ 10 июля 2009

Ну, версия будет:

  1. перевернуть список
  2. удалить ведущий ноль
  3. перевернуть список

код: 

(defun list-right-trim (list &optional item)
  (setf list (reverse list))
  (loop for e in list while (eq item e) do (pop list))
  (reverse list))

Вот еще один вариант:

  1. переберите список и отметьте позицию первого нуля, за которым следует только ниль
  2. вернуть подпоследовательность

код: 

(defun list-right-trim (list &aux (p nil))
  (loop for i from 0 and e in list
    when (and (null p) (null e)) 
    do (setf p i)
    else when (and p e) do (setf p nil))
  (if p (subseq list 0 p) list))
2 голосов
/ 11 июля 2009

Как насчет этого? 

(defun strip-tail (lst)
  (if lst
    (let ((lst (cons (car lst) (strip-tail (cdr lst)))))
      (if (not (equal '(nil) lst)) lst))))

... интересно, как сделать хвостовую рекурсию, хотя эта версия исчерпала бы стек для больших списков.

1 голос
/ 10 июля 2009

Вот то, что я придумал, если вы не возражаете против этого разрушительного: 

(defvar foo (list 'a 'b 'c nil 'd 'e 'nil 'nil 'f nil nil))

(defun get-last-non-nil (list &optional last-seen)
  (if list
      (if (car list)
          (get-last-non-nil (cdr list) list)
          (get-last-non-nil (cdr list) last-seen))
      last-seen))

(defun strip-tail (list)
  (let ((end (get-last-non-nil list)))
    (if (consp end)
        (when (car end) (setf (cdr end) nil) list))))

(strip-tail foo) -> (A B C NIL D E NIL NIL F)
0 голосов
/ 10 июля 2009

Ну, на самом деле это не ответ, но я подумал, что я бы также поместил его здесь, чтобы он был лучше виден.

Как вы думаете, в исходной реализации должны обрабатываться элементы не из списка? 

* (strip-tail "abcde")

"abcde"
* (strip-tail 42)

debugger invoked on a TYPE-ERROR in thread #<THREAD "initial thread" {A69E781}>:
  The value 42 is not of type SEQUENCE.
0 голосов
/ 10 июля 2009

Я пытался использовать рекурсию, но она не работает в GNU CL: 

(defun strip(lst) 
    (if (null (last lst))
        (strip (butlast lst))            
     lst))

Идея такова:

  1. проверить, равен ли последний элемент списка нулю, если таксделать рекурсивный вызов с последним удаленным элементом ( butlast )
  2. , а затем вернуть сам список
...