How can I combine elements from 2 lists in LISP?

Question

Given 2 lists, how can you create the output of a 3rd list that has elements in the form of an interleaved set of L1 and L2? if they have an uneven length, zero should be inserted for holes. On the second note, how can I cancel the list? I am super new to LISP and just modifying existing code ... I would love to have a good explanation, not just the code.

Answer 1

First, I assume you are using Common Lisp, as it is most often used in Lisp courses. So my examples will be in CL. If you use Scheme, you will get almost the same code. If modern Clojure, he will need some changes, through the idea will be the same.

Alternation

To alternate 2 lists, you must go through both of them, collecting items in turn. You can use a loop operator or recursion for this. I will use recursion because it has a more functional style and can be used in any Lisp, and not just in the CL. Also note that there is a tail recursion function that allows you to write a recursive function to be compiled in a loop.
Thus, the basic skeleton for our function will be:

(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

Reverse

: 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 ( ^ 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 - ). , :

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

:from-end , , : initial-value , nil.

: :from-end true , , , reverse-1-2.

Answer 2

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 nil) (cons nil (interleave l2 l1)))

:   ((null l1) l2)

:

Answer 4

An example of a more idiomatic solution in 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))))