Functional/idiomatic way to express this Python in Clojure
Question: I have a data transformation that is leaving me a bit stymied. I wasn't able
to express myself in Clojure and even my Python, that I'm fluent in, still
feels quite gross.

I need a data structure like:

    
    
    [1, 2, [3, 4], 5, 6]
    

to generate a structure like this:

    
    
    [[1, 2, 3, 5, 6]
     [1, 2, 4, 5, 6]]
    

where each sub-collection creates a new collection with the items accumulated
thus far. I only expect a single level of nesting.

My python attempt looks like this:

    
    
    def foo(path, acc_list=[[]]):
        for val in path:
            if not isinstance(val, list):
                for acc in acc_list:
                    acc.append(val)
            else:
                for subval in val:
                    new = acc_list[0][:]
                    new.append(subval)
                    acc_list.append(new)
                del acc_list[0]
        return acc_list
    
    foo([1, 2, [3, 4], 5, 6])
    # => [[1, 2, 3, 5, 6], [1, 2, 4, 5, 6]]
    

I'd like to know what a Clojure solution would be and (more importantly) the
thinking that led to that solution.

_update_

  * The ints are just for example, they could be keywords or strings too and not necessarily ordered, although order must obviously be preserved.

  * by nesting, I meant it won't be like `[1 [2 [3 [4 5] 6] 7] 8]` but more like `[1 [2 3] 4 [5] 6 [7 8 9]]` \- shallow.


Answer: An important feature of many of the Clojure core library functions is the
ability to handle lazy (potentially infinite) sequences; therefore, I would
think that a good (idiomatic) Clojure solution would be able to properly
expand an input containing subsequences that are infinite lazy sequences. For
example:

    
    
    [:a :b (range) :c]
    

Should expand to

    
    
    ((:a :b 0 :c) (:a :b 1 :c) (:a :b 2 :c) (:a :b 3 :c) ...)
    

It would be great if the top-level sequence could also be infinite and handled
lazily, however, I don't think that is possible for this problem. (But if
someone else can think of a way to practically handle that, I'll be
delightfully surprised!)

Here's my solution:

    
    
    (defn expand-subseqs [[x & xs]]
      (when-not (nil? x)
        (let [heads (if (sequential? x) x [x])
              tails (expand-subseqs xs)]
          (if-not tails (map vector heads)
            (for [z tails, y heads] (cons y z))))))
    

The intuition here is that you recursively handle the tail of the input
sequence first, and then you prepend each possible value for the current head
onto each possible tail.

Some sample outputs:

    
    
    user=> (expand-subseqs [1, 2, [3, 4], 5, 6])
    ((1 2 3 5 6) (1 2 4 5 6))
    user=> (take 5 (expand-subseqs [:a :b (range) :c [true false]]))
    ((:a :b 0 :c true) (:a :b 1 :c true) (:a :b 2 :c true) (:a :b 3 :c true) (:a :b 4 :c true))
    

A nice benefit of this solution is that, by using `cons`, we actually reuse
the objects representing the tail sequences for each result, rather than
duplicating the whole sequence for each permutation. For example, in the last
sample above, the `(:c true)` tail sequence in every one of the five outputs
is actually the same object.

