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]
[[1, 2, 3, 5, 6]
[1, 2, 4, 5, 6]]
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]]
[1 [2 [3 [4 5] 6] 7] 8]
[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.