Как объединить элементы из 2 списков в LISP?

Question

Учитывая 2 списка, как вы можете создать вывод 3-го списка, который имеет свои элементы в виде чередующихся наборов L1 и L2? если они имеют неровную длину, нуль следует вставлять для отверстий. На второй ноте, как можно отменить список? Я супер новичок в LISP и просто модифицирую существующий код ... Мне очень понравилось бы иметь хорошее объяснение, а не только код.

Answer 1

Во-первых, я предполагаю, что вы используете Common Lisp, так как он наиболее часто используется в курсах Лиспа. Итак, мои примеры будут в CL. Если вы используете Scheme, вы получите почти тот же код. Если современный Clojure, ему понадобятся некоторые изменения, через идею будет то же самое.

Interleave

чередовать 2 списка вы должны пройти через оба из них, собирая элементы по очереди. Для этого вы можете использовать оператор цикла или рекурсию. Я буду использовать рекурсию, поскольку она имеет более функциональный стиль и может использоваться в любом lisp, а не только в CL. Также обратите внимание, что есть функция, называемая tail recursion, которая позволяет записывать рекурсивную функцию, которая будет скомпилирована в цикле.
Таким образом, базовый каркас для нашей функции будет:

(defun interleave (l1 l2) 
    ?????? 
     (interleave ?????)) 

Чтобы собрать элементы в рекурсивных функциях, нужно будет возвращать их из каждого вызова, а затем минусы вместе (для хвостовой рекурсии необходимо иметь еще один параметр, который будет накапливать значения). Итак, конец функции будет (cons current-value (interleave ????)). Также вы должны чередовать списки, чтобы брать элементы друг от друга. У вас может быть дополнительный параметр, но вы также можете просто поменять их на рекурсивный вызов. Таким образом, код становится следующим:

(defun interleave (l1 l2) 
    ????? 
    (cons current-value (interleave l2 l1))) 

Любая рекурсия должна где-то остановиться. В этом случае он должен остановиться, когда оба списка пусты (nil). Это одно условие (дайте ему номер 1), и есть еще несколько условий:
2. Если список, который нужно взять, пуст, а другой нет, мы должны взять нуль вместо этого.
3. Если оба списка не пусты, возьмите первый элемент как текущее значение и продолжите его хвост.

Есть только еще одно условие, в котором могут быть 2 списка: список, который нужно взять, не пуст, а второй. Но на самом деле мы не беспокоимся об этом и может идти вперед с рядом правил 3. Таким образом, код (и это является окончательным):

(defun interleave (l1 l2) 
    (cond ((and (eql l1 nil) (eql l2 nil)) nil)   ;; rule #1 
     ((eql l1 nil) (cons nil (interleave l2 l1))) ;; rule #2, current value is nil 
     (true (cons (first l1) (interleave l2 (rest l1)))))) ;; rule #3 in all other cases 

Обратный

Я Здесь показаны две реализации этой функции: одна с cond и другая с встроенной функцией reduce, которая чрезвычайно полезна на практике.

Первый подход к cond версии пройти через весь список с рекурсивными вызовами, а затем вернуться назад, собирая элементы:

(defun reverse-1-1 (li) 
    (if (eql li nil) 
     nil 
     (append (reverse-1-1 (rest li)) 
       (list (first li))))) 

Но это крайне неэффективно, так как Append является O(n), и вы должны пройти n элементов, поэтому конечная сложность O (n^2).

Чтобы уменьшить его, вы можете использовать еще один аргумент функции (и сделать его хвост рекурсивной, если компилятор позволяет вам):

(defun reverse-1-2 (li) 
    (reverse-aux li nil)) 

(defun reverse-aux (li accumulator) 
    (if (eql li nil) 
     accumulator 
     (reverse-aux (rest li) (cons (first li) accumulator)))) 

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

Есть еще один интересный вариант. Lisp имеет чрезвычайно мощную функцию reduce (в других функциональных языках ее иногда называют fold, foldr, foldl или что-то в этом роде). Вы можете найти описание для этого here, и я просто покажу пример:

(defun reverse-2 (li) 
    (reduce #'cons li :from-end t :initial-value nil)) 

:from-end говорит функцию, чтобы пройти через список с конца, а также: начальное значение говорит использовать как очень первый уменьшенный аргумент nil.

Примечание: в некоторых реализациях уменьшить с помощью опции :from-end true можно сначала создать обратный список, поэтому, если вам нужно создать его с нуля или использовать наиболее эффективную версию, вместо этого используйте reverse-1-2.

Answer 2

В Common Lisp:

(defun merge-lists (lst1 lst2) 
    (let ((m (max (length lst1) (length lst2)))) 
    (flatten (mapcar (lambda (a b) (list a b)) 
        (append-nulls lst1 m) 
        (append-nulls lst2 m))))) 

Примеры:

(merge-lists '(1 2 3 4) '(5 6 7 8)) ;; => (1 5 2 6 3 7 4 8) 
(merge-lists '(1 2 3 4) '(5 6 7)) ;; => (1 5 2 6 3 7 4 NULL) 
(merge-lists '(1 2) '(5 6 7 8)) ;; => (1 5 2 6 NULL 7 NULL 8) 

Вспомогательные функции flatten и append-nulls:

(defun flatten (tree) 
    (let ((result '())) 
    (labels ((scan (item) 
       (if (listp item) 
        (map nil #'scan item) 
        (push item result)))) 
     (scan tree)) 
    (nreverse result))) 

(defun append-nulls (lst n) 
    (if (< (length lst) n) 
     (dotimes (i (- n (length lst))) 
     (setq lst (append lst (list 'null))))) 
    lst) 

Answer 3

Ответ выше:

(defun interleave (l1 l2) 
    (cond ((and (eql l1 nil) (eql l2 nil)) nil)   ;; rule #1 
     ((eql l1 nil) (cons nil (interleave l2 l1))) ;; rule #2, current value is nil 
     (true (cons (first l1) (interleave l2 (rest l1)))))) ;; rule #3 in all other cases 

Если один из ваших списков длиннее другого, вы получите что-то вроде (1 2 3 4 ноль 5). Заменить: ((EQL l1 ноль) (минусы ноль (перемежать L2 L1)))

с: ((нулевая l1) l2)

: Р

Answer 4

Примером более идиоматичен решение в Common Lisp:

(defun interleave (a b) 
    (flet ((nil-pad (list on-list) 
      (append list (make-list (max 0 (- (length on-list) (length list))))))) 
    (loop for x in (nil-pad a b) 
      for y in (nil-pad b a) 
      append (list x y))))