Clojure: Semi-Flattening a nested Sequence

Question

I have a list with embedded lists of vectors, which looks like:

(([1 2]) ([3 4] [5 6]) ([7 8]))

Which I know is not ideal to work with. I'd like to flatten this to ([1 2] [3 4] [5 6] [7 8]).

flatten doesn't work: it gives me (1 2 3 4 5 6 7 8).

How do I do this? I figure I need to create a new list based on the contents of each list item, not the items, and it's this part I can't find out how to do from the docs.

Solution 1

If you only want to flatten it one level you can use concat

(apply concat '(([1 2]) ([3 4] [5 6]) ([7 8])))
=> ([1 2] [3 4] [5 6] [7 8])

Solution 2

To turn a list-of-lists into a single list containing the elements of every sub-list, you want apply concat as nickik suggests.

However, there's usually a better solution: don't produce the list-of-lists to begin with! For example, let's imagine you have a function called get-names-for which takes a symbol and returns a list of all the cool things you could call that symbol:

(get-names-for '+) => (plus add cross junction)

If you want to get all the names for some list of symbols, you might try

(map get-names-for '[+ /]) 
=> ((plus add cross junction) (slash divide stroke))

But this leads to the problem you were having. You could glue them together with an apply concat, but better would be to use mapcat instead of map to begin with:

(mapcat get-names-for '[+ /]) 
=> (plus add cross junction slash divide stroke)

Solution 3

The code for flatten is fairly short:

(defn flatten
  [x]
  (filter (complement sequential?)
    (rest (tree-seq sequential? seq x))))

It uses tree-seq to walk through the data structure and return a sequence of the atoms. Since we want all the bottom-level sequences, we could modify it like this:

(defn almost-flatten
  [x]
  (filter #(and (sequential? %) (not-any? sequential? %))
    (rest (tree-seq #(and (sequential? %) (some sequential? %)) seq x))))

so we return all the sequences that don't contain sequences.

Solution 4

Also you may found useful this general 1 level flatten function I found on clojuremvc:

(defn flatten-1 
  "Flattens only the first level of a given sequence, e.g. [[1 2][3]] becomes
   [1 2 3], but [[1 [2]] [3]] becomes [1 [2] 3]."
  [seq]
  (if (or (not (seqable? seq)) (nil? seq))
    seq ; if seq is nil or not a sequence, don't do anything
    (loop [acc [] [elt & others] seq]
      (if (nil? elt) acc
        (recur
          (if (seqable? elt)
            (apply conj acc elt) ; if elt is a sequence, add each element of elt
            (conj acc elt))      ; if elt is not a sequence, add elt itself 
       others)))))

Example:

(flatten-1 (([1 2]) ([3 4] [5 6]) ([7 8])))
=>[[1 2] [3 4] [5 6] [7 8]]

concat exampe surely do job for you, but this flatten-1 is also allowing non seq elements inside a collection:

(flatten-1 '(1 2 ([3 4] [5 6]) ([7 8])))
=>[1 2 [3 4] [5 6] [7 8]]
;whereas 
(apply concat '(1 2 ([3 4] [5 6]) ([7 8])))
=> java.lang.IllegalArgumentException: 
   Don't know how to create ISeq from: java.lang.Integer

Solution 5

Here's a function that will flatten down to the sequence level, regardless of uneven nesting:

(fn flt [s] (mapcat #(if (every? coll? %) (flt %) (list %)) s))

So if your original sequence was:

'(([1 2]) (([3 4]) ((([5 6])))) ([7 8]))

You'd still get the same result:

([1 2] [3 4] [5 6] [7 8])

View more solutions

Comments

[jm0]

yea +1 for mapcat -- it led to a MUCH more elegant solution than i would have had otherwise. very good to know. thanks!

[Post Self]

I am using map-indexed, though and there is no mapcat-indexed

[amalloy]

@PostSelf map-indexed is just a shorthand for adding an argument to map. Instead of (apply concat (map-indexed f xs)), try (mapcat f (range) xs).

[Post Self]

@amalloy That's awesome! I realized that I do a filter based on the second element of each pair, so unless there's a way of incorporating that, I have to leave it as is

[amalloy]

@PostSelf There is, of course! mapcat is sorta a "fundamental" list operation on which many others can be built. Instead of (apply concat (filter (comp pred second) (map-indexed f xs))), you can write (mapcat (fn [i x] (let [x' (f x)] (when (pred x') [i x']))) (range) xs).

[Alper]

mapcat is the MVP.

[Siraj K]

(def balls '((:a 1) ((:b 1) (:c 1)))) Not exactly: (apply concat balls) => (:a 1 (:b 1) (:c 1)) Perfect: (almost-flatten balls) => ((:a 1) (:b 1) (:c 1))