How would one interleve elements of 2 lists in LISP?

Question

Given 2 lists, how can you produce an output of a 3rd list which has it's elements as an interleaved set of L1 and L2? if they are uneven length, nil should be inserted for holes. On a second note, how can I reverse a list? I've super new to LISP and simply modifying existing code... I'd really love to have a good explanation, not just code.

Answer 1

First, I guess you use Common Lisp, as it is the one most 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, it will need some changes, through an idea will be the same.

Interleave

To interleave 2 lists you must go through both of them, collecting elements by turns. You can use loop statement or recursion for this. I'll use recursion since it has more functional style and may be used in any lisp, not only CL. Also note, that there's a feature called tail recursion, which lets you write recursive function that will be compiled to a loop.
So, base skeleton for our function will be:

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

To collect items in recursive functions you will need to return them from each call and then cons together (for a tail recursion you must have one more parameter, which will accumulate values). So, the end of the function will be (cons current-value (interleave ????)). Also you must alternate lists to take elements from with each other. You may have additional parameter, but you also may just swap them in a recursive call. So, code becomes:

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

Any recursion must stop somewhere. In this case, it must stop when both lists are empty (nil). This is one condition (let give it number 1), and there are some more conditions:
2. if the list to take from is empty, and the other one is not, we must take nil instead.
3. if both lists are not empty, take first element as a current-value and proceed with it's tail.

There's only one more condition that 2 lists can be in: list to take from is not empty, and the second one is. But in fact we don't care about this and may go forward with a rule number 3. So, the code (and this is the final one):

(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

I'll show two implementations of this function: one with cond and another with built-in reduce function which is extremely useful in practice.

First approach for cond version is to go through the all list with a recursive calls and then go back, collecting elements:

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

But this is extremely inefficient, since append is O(n), and you must pass n elements, so the final complexity is O(n^2).

To reduce it you may use one more argument to the function (and make it tail recursive, if compiler lets you):

(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))))

That's you use one more parameter to collect your elements in while passing through the list, and then just return this accumulator.

There's one more interesting option. Lisp has extremely powerful function reduce (in other functional languages it is sometimes called fold, foldr, foldl or something like that). You may find description for it here, and I'll just show an example:

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

:from-end tells function to go through the the list from the end, and :initial-value tells to use as the very first reduced argument nil.

Note: in some implementations reduce with option :from-end true may first reverse list by itself, so if you need to create it from scratch or use the most efficient version, use reverse-1-2 instead.

Answer 2

In 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)))))

Examples:

(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)

The helper functions flatten and 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)