CODEWITHSUNDEEP
pythonclojuretransformation
lsh
lsh

Reputation: 658

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

Upvotes: 1

Views: 92

Answers (2)

DaoWen
DaoWen

Reputation: 33029

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.

Upvotes: 2

jmargolisvt
jmargolisvt

Reputation: 6088

I'm sure there are other ways to do this, but here is one way.

user.core=> (def x [1, 2, [3, 4], 5, 6])
#'user.core/x
user.core=> (defn create-vecs [x]
         =>   (let [sub (first (filter vector? x))
         =>         all (remove vector? x)]
         =>   (vec (map #(vec (sort (conj all %))) sub))))
#'user.core/create-vecs
user.core=> (create-vecs x)
[[1 2 3 5 6] [1 2 4 5 6]]

Basically, you are grabbing the vector element and the rest of the vector minus the vector element, then mapping over them to create the two new vectors with conj. You need the extra vec's in there because filter and remove return lists, not vectors.

Upvotes: 1

Related Questions