Functional/idiomatic way to express this Python in Clojure
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 but more like
[1 [2 [3 [4 5] 6] 7] 8]- shallow.[1 [2 3] 4 [5] 6 [7 8 9]]
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.