Практика Lisp

Question

Я начал изучать Lisp 2 дня назад, и я читаю обычный список ANSI Пол Грэма, который очень интересен для языка. Это не слишком много теоретических для новичков, и не слишком мелко (как глава Сьерра-Бэйт First Java, которого лично я ненавижу). После краткого общего введения языка он начинает говорить списки ботов и поднимает пример простого сжатия списка. В принципе, пусть el - это элемент, который повторяется n раз. Вы заменяете все их одним (n el) списком. Для этого он дал реализацию кода, но я попытался сделать свое, что, по-видимому, работает. По возможности я хотел бы, чтобы кто-то анализировал мой код и показывал мне критические моменты его реализации, и я уверен, что их много, так как это мой первый контакт с Lisp. Спасибо всем!

(defun compress (x) 
"compress a list replacing repeated sequential values for (<n> <value>)" 
(let ((lst '()) (fst t) (lt nil) (n 0)) 
    (dolist (el x) 
     (if fst 
      (progn 
       (setq fst nil) 
       (setq lt el) 
       (setq n 1)) 
      (progn 
       (if (equal el lt) 
        (setq n (+ n 1)) 
        (progn 
         (setq lst (cons (if (= n 1) 
            lt 
            (list n lt)) 
           lst)) 
         (setq lt el) 
         (setq n 1) 
        ))))) 
    (setq lst (cons (if (and (not (= n 0)) (= n 1)) 
         lt 
         (list n lt)) 
      lst)) 
(reverse lst))) 

Answer 1

Алгоритм кажется вполне разумным. Я нахожу только переменную fst. Вы используете его только при входе в цикл, чтобы вы могли просто перенести первую связку назначений в преамбулу и перебрать остальные элементы списка.

Теперь вопрос заключается в том, как выразить алгоритм в Lisp.

Наиболее важным моментом является то, что вы можете использовать nreverse вместо reverse. nreverse более эффективен, но он разрушает структуру своих аргументов. Как правило, вы не хотите этого из-за так называемой общей структуры: ячейка cons может быть частью нескольких списков, поэтому изменение продаж cons может привести к неожиданным изменениям в явно несвязанных списках. (PCL очень хорошо относится к этой проблеме.) Однако в вашей функции вы создаете lst с нуля, вручную нажимая на нее новые элементы, поэтому он не может совместно использовать структуру с другими списками. Таким образом, вы можете спокойно обойтись без структуры. Это общая идиома push/nreverse. reverse просто вникает в новый список, а lst становится мусором.

Чтобы сделать код более идиоматическим, вы можете использовать стандартные ярлыки как incf для += и push для cons=. В настоящее время универсальный setf, по-видимому, более популярен, чем setq. Лично я предпочитаю использовать cond, где в противном случае появится progn. Таким образом, вы могли бы в конечном итоге с чем-то вроде этого:

(defun compress (x) 
    "compress a list replacing repeated sequential values for (<n> <value>)" 
    (if x 
     (let ((lst '()) 
      (lt (first x)) 
      (n 1)) 
     (dolist (el (rest x)) 
      (cond ((equal el lt) (incf n)) 
       (t (push (if (= n 1) 
          lt 
          (list n lt)) 
         lst) 
        (setf lt el) 
        (setf n 1)))) 
     (push (if (= n 1) 
        lt 
        (list n lt)) 
       lst) 
     (nreverse lst)) 
     nil)) 

Answer 2

В дополнение к Stanislav's answer Я хотел бы показать еще одну возможную реализацию. Алгоритм сжатия является идеальным прецедентом для REDUCE, также известного как fold. Функция уменьшения принимает результат до сих пор, новый элемент и объединяет их для получения следующего результата. В результате вы получите список пар. Исходным элементом является пустой список. Снижение

(defun compress (sequence) 
    (reduce (lambda (number list &aux (head (first list))) 
      (if (eql number (first head)) 
       (prog1 list 
        (incf (second head))) 
       (cons (list number 1) list))) 
      sequence 
      :from-end t 
      :initial-value nil)) 

применяется с конца, так что вы можете легко cons новая пара на верхней части текущего результата при сохранении существующего порядка элементов.Если вход '(a b b c), то восстановитель функции анонимный будет называться следующим образом:

number list   new list 
--------------------------------------------- 
c  nil   ((c 1)) 
b  ((c 1))  ((b 1)(c 1)) 
b  ((b 1)(c 1)) ((b 2)(c 1)) 
a  ((b 2)(c 1)) ((a 1)(b 2)(c 1)) 

REDUCE определяются для последовательностей, функция сжатия является родовой:

;; string 
(compress "aaddzadzaaaddb") 
=> ((#\a 2) (#\d 2) (#\z 1) (#\a 1) (#\d 1) (#\z 1) (#\a 3) (#\d 2) (#\b 1)) 

;; vector 
(compress #(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5)) 
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6)) 

;; list 
(compress '(1 2 3 3 3 3 4 4 4 55 5 5 5 5 5 5)) 
=> ((1 1) (2 1) (3 4) (4 3) (55 1) (5 6))