Adding List items together while using provisional result

Question

I have the following list:

((a b) (c d) (e f))

and want to loop through it and combine the list elements together. I also have the loop for that, which works exactly like I want to:

(loop for (x . tail) on l1
      append (loop for y in tail
                   collect (append (list '&)  x y)))

The problem is, that I want to first add the first two elements,

((a b) (c d)) -> ((& a b ) (& c d) (& a b c d))

and use this provisional result to add the next list, (e f) to it.

((a b ) (c d) (a b c d) (e f)) -> ((& a b e f) (& c d e f) (& a b c d e f))

Would I have to write an extra function, that calls the lop with two elements first or is there a kind of loop variable to use a provisional result? I've tried using an extra function but it just seems so wordy and unnatural. I'm really new to Lisp Loops

Answer 1

The Problem Statement

The OP requirements are murky. Given an input list it isn't entirely clear what the output should be; this is compounded by inconsistencies in the example outputs provided by OP in the question and comments.

OP starts from a loop that combines the elements of an input list:

(loop for (x . tail) on l1
      append (loop for y in tail
                   collect (append (list '&)  x y)))

This loop will not produce pairs of the sort shown in OP expected output:

((a b) (c d)) -> ((& a b ) (& c d) (& a b c d))

Instead, the output of the above is:

((a b) (c d)) -> ((& a b c d))

The final result of operating on ((a b) (c d) (e f)) appears to be ((& a b e f) (& c d e f) (& a b c d e f)). But this seems to be missing the list (& a b c d).

In the comments is appears that the result of operating on the list ((a b) (c d) (e f) (g h)) should be ((& a b) (& c d) (& a b c d) (& a b e f) (& c d e f) (& a b c d e f) (& a b g h) (& c d g h) (& a b c d g h) (& a b e f g h) (& c d e f g h) (& a b c d e f g h)). This result includes the lists (& a b) and (& c d), which don't seem to have any connection to the original operation. Further, (& e f) and (& g h) are mysteriously absent in this result.

From this, though, it seems that the OP desires to collect a result containing all of the original combinations generated by the first operation together with the result of operating on a series of lists reduced by cdr and transformed by concatenating the first pair of each list.

A Possible Solution

I don't claim that this is an optimal solution, a particularly good solution, or that it even solves OP's problem as it is not very clearly laid out here. I only claim that this may be a solution which uses OP's original combining operation and that is reasonably clear. I suspect that a better solution might be found by rethinking the problem from the beginning.

The OP operation can be placed in a function:

(defun combiner (xss)
  (loop for (x . tail) on xss
        append (loop for y in tail
                     collect (append x y))))

Here the added symbol '& is ignored; that will only confuse matters while we are combining list elements, and a symbol can easily be prepended to the result lists when we are done.

There is no need to use combiner to operate on the first two elements of a list since the result is always just the concatenation of those two list elements. It would be useful to write a function that transforms a list by concatenating the first two elements. Singleton lists should be transformed to nil:

(defun fancy-transform (xss)
  (unless (null (cdr xss))
    (cons (append (first xss) (second xss))
          (cddr xss))))

Now we are ready to write a function that uses combiner to create the desired result:

(defun fancy-combiner (xss)
  (mapcar (lambda (xs) (cons '& xs))
          (remove-duplicates
           (loop for uss on xss
                 append (loop for vss on uss by #'fancy-transform
                              append (combiner vss)))
           :test #'equal)))

The action is in the loop macro here. The call to remove-duplicates is needed since the result of the loop contains duplicates, and the call to mapcar is used to prepend '& symbols to each list in the result.

The outer loop feeds progressively smaller versions of the input list to the inner loop; each of these lists is transformed by combiner, then reduced by fancy-transform, which reduces the list by appending the first two elements or returning nil when a singleton list is reached (ending that iteration).

It may help to see the progress as an input list is processed. This fancy-combiner-illustrated function does not remove duplicates or prepend a symbol to the lists in the result:

(defun fancy-combiner-illustrated (xss)
  (loop for uss on xss
        do (format t "~%USS: ~A" uss)
        append (loop for vss on uss by #'fancy-transform
                     do (format t "~%VSS: ~A" vss)
                     append (combiner vss))))

CL-USER> (fancy-combiner-illustrated '((a b) (c d) (e f) (g h)))

USS: ((A B) (C D) (E F) (G H))
VSS: ((A B) (C D) (E F) (G H))
VSS: ((A B C D) (E F) (G H))
VSS: ((A B C D E F) (G H))
VSS: ((A B C D E F G H))
USS: ((C D) (E F) (G H))
VSS: ((C D) (E F) (G H))
VSS: ((C D E F) (G H))
VSS: ((C D E F G H))
USS: ((E F) (G H))
VSS: ((E F) (G H))
VSS: ((E F G H))
USS: ((G H))
VSS: ((G H))
((A B C D) (A B E F) (A B G H) (C D E F) (C D G H) (E F G H) (A B C D E F)
 (A B C D G H) (E F G H) (A B C D E F G H) (C D E F) (C D G H) (E F G H)
 (C D E F G H) (E F G H))

The lists VSS are the ones operated on by combiner, and since many of these list have tails that are the same, duplicates occur in the result. The fancy-combiner function uses remove-duplicates to remove these duplicates before prepending the '& symbol to each list in the result.

Results

CL-USER> (fancy-combiner '((a b) (c d)))
((& A B C D))

CL-USER> (fancy-combiner '((a b) (c d) (e f)))
((& A B C D) (& A B E F) (& A B C D E F) (& C D E F))

CL-USER> (fancy-combiner '((a b) (c d) (e f) (g h)))
((& A B C D) (& A B E F) (& A B G H) (& A B C D E F) (& A B C D G H)
 (& A B C D E F G H) (& C D E F) (& C D G H) (& C D E F G H) (& E F G H))

These aren't exactly the results indicated by OP in the question and comments, but since there seem to be inconsistencies in OP comments it is hard to know exactly what is expected.

Would I Have to Write an Extra Function?

Assuming the this solution does match OP expectations, you could write the whole thing as one function by using a lambda expression in place of fancy-transform and replacing the call to combiner in fancy-combiner with the equivalent loop expression. There is no benefit to that, and the resulting code would be less clear.

OP asks: "is there a kind of loop variable to use a provisional result?", but it seems that OP desires to change the input list as it is processed, e.g., by inserting (a b c d) into the input list at some point during the traversal of the input. This is not possible in Common Lisp; it is forbidden to destructively modify any list during a traversal operation. The loop facility does not provide any mechanism for this.

Answer 2

I started to solve this during a train ride where I had no internet. So when I arrived the other answer was there. But nevertheless, I will post my construct.

((a b) (c d) (e f) (g h))
;; => ((a b) (c d) (e f) (g h)
;;     (a b c d) (a b e f) (c d e f) (a b g h) (c d g h)
;;     (a b c d e f) (a b c d g h) 
;;     (a b e f g h) 
;;     (c d e f g h) 
;;     (a b c d e f g h))

The first row is the list as it is. The second row is pairings of the elements of this list - but only with the parts cdr of the last element. The third to before-last row is pairings with the second row and the cdr of the list. And the last row is unification of everything.

(defun once-flatten (lol)
  (loop for x in lol
        if (atom x)
          collect x
        else
          append x))
        
(defun list-and-pairings* (list) ;; or #'append
  (append list
          (mapcar #'once-flatten
                  (loop for (x . tail) on list
                        append (loop for y in (if (> (length tail) 1)
                                                  (list-and-pairings* tail)
                                                  tail)
                                     collect (list x y))))))

(defun add-& (lol) (mapcar (lambda (x) (if (atom x) x (cons '& x))) lol))

And then we can do:

(add-& (list-and-pairings* '((a b) (c d) (e f) (g h))))
;; => ((& A B) (& C D) (& E F) (& G H) 
;;     (& A B C D) (& A B E F) (& A B G H)
;;     (& A B C D E F) (& A B C D G H) (& A B C D E F G H) (& A B E F G H)
;;     (& C D E F) (& C D G H) (& C D E F G H) (& E F G H))

One can also use:

(defun add-& (lol)
 (loop for x in lol
       if (atom x)
         collect x
       else
         collect (cons '& x)))