Sparsely populated multidimensional vector in clojure?

Question

I'm trying to create a sparsely populated multidimensional vector in Clojure, but I'm coming up against the limits of my knowledge.

I have a collection x I'm iterating over, and I want to create a multidimensional vector of size (count x) by (count x). Most of the cells will be empty, but at each point where the x and y axes match (e.g., (1 1), (2 2), (3 3), etc.), I need to run a function to see if a value should be put in that space.

In a procedural language, it would be something like:

for (i = 0; i < length(x); i++) {
    for (j = 0; j < length(x); j++) {
        if (i == j && testReturnsTrue(x[i])) {
            table[i][j] = (list x[i])
        }
        else {
            table[i][j] = ()
        }
    }
}

But I can't wrap my head around how this would be done in Clojure. I tried using nested for comprehensions and nested loop-recur structures but I can't get either to work.

Alternatively, I could create a mutable table with the right sizes, initialize it all to empty lists, and then set the values as I check each element in x, but I'd like to keep the table immutable if possible.

Answer 1

Use a hashmap? There's no need for a vector, which can't be sparse. Plus, this imperative solution looks like it's not sparse either - it's wasting memory storing zillions of empty cells. Perhaps something like this:

(let [indexed (map-indexed vector xs)]
  (reduce (fn [m [i x]]
            (if (test? x)
              (assoc-in m [i i] x)
              m))
          {}
          indexed))

Answer 2

Nested fors is how I would do it:

(def x [:a :b :c :d])
(vec (for [i (range (count x))]
       (vec (for [j (range (count x))]
              (if (and (= i j) (identity (x i)))
                [(x i)]
                [])))))
=> [[[:a] [] [] []] [[] [:b] [] []] [[] [] [:c] []] [[] [] [] [:d]]]

(identity (x i)) is a stand-in for some kind of test.

EDIT: As mentioned in other answers, if this structure remains sparsely populated, a hash-map is a better choice. I was assuming you would be populating the empty portions in later computations.