How do you unfold a nested Julia array?

General Usage
1

What is an efficient, elegant, Julian way to unfold a nested array:

nested = [[1,2,3],[4,5]]
vcat(nested...) # works but not always

Is there a function in Base to unfold all sorts of nested data structures into a plain list of items?

1 Like
2

It sounds like you are looking for Compat.Iterators.flatten (i.e. Base.flatten in 0.5, Base.Iterators.flatten in 0.6).

5 Likes
3

It seems that flatten() returns an iterator, so you might need collect(flatten()).

Also it seems flatten() works for only 1 nested level.
If you need to flatten deeper nested levels, then something recursive might work:

function unfold(A)
    V = []
    for x in A
        if x === A
            push!(V, x)
        else
            append!(V, unfold(x))
        end
    end
    V
end

Totally untested, but seems to work for the following:

a = ((1,),2)
b = 3:4
c = [5,[6,[7,8]],9]
A = (a,b,c)
unfold(A)
3 Likes
4

Maybe this?
https://gist.github.com/ivirshup/e9148f01663278ca4972d8a2d9715f72

1 Like
5

Thanks @greg_plowman, I marked @fengyang.wang answer as the solution in Base, but it is good to have your solution for multi-level nested structures too.

6

Thanks @stst, I believe @greg_plowman solution does the same and works for other types other than Arrays.

7

My way of doing this:

function deepflatten(arr)
    dim = [1]

    function recursiveflatten(arr, dim)
        if isa(arr, Vector{<: Vector})
            recursiveflatten(
                collect(Iterators.flatten(arr)),
                pushfirst!(dim, length(arr) / prod(dim))
            )
        else
            arr, pushfirst!(dim, length(arr) / prod(dim))
        end
    end

    flattened, dim = recursiveflatten(arr, dim)
    reshape(flattened, dim[1:end-1]...)
end
1 Like
8

For arbitrary nesting like x = [[1,2], [3, [4, [5]]]], what I ended up doing was

using AbstractTrees
x = [[1, 2], [3, [4, [5]]]]
v = collect(Leaves(x)) # [1, 2, 3, 4, 5]
9

In Rosetta code there is a fast solution:

flat(arr) = mapreduce(x -> x == [] || x[1] === x ? x : flat(x), vcat, arr, init=[])

x = [[1,2], [3, [4, [5]]]]
y = ((1,2), (3, (4, (5))))
z = (((1,),2), 3:4, [5,[6,[7,8]],9])
w = (("ab", 'c'), 1:3)

flat(x)
flat(y)
flat(z)
flat(w)
1 Like
10 
using IterTools
flatn(w)=collect(nth(iterated(Base.Flatten,w),length(split(string(w),['[','(']))))
11

If you have a nested Tuple, where all elements are values or Tuples (not vectors),
this is a performant and memory respectful solution. As written, it returns a Vector. To obtain a tuple, use
result = Tuple(flattener(nestedtuples))

using TupleTools

function flattener(x)
  y = TupleTools.flatten(x)
  n = sum(length.(y))
  z = Vector{Any}(undef, n)
  i=1; for k in y
      if isa(k, Tuple)
         for r in k
             z[i] = r
         end
      else
         z[i] = k
      end
      i += 1
   end
   z
end
1 Like
12

if I understand correctly this function is based on something like the following.
Why can’t it also apply to generic vectors?

flat(x::Any)=(x,)
flat(t::Tuple{}) = ()
flat(t::Tuple)=(flat(t[1])...,flat(Base.tail(t))...)
13

this one (which I’ve come to by trial and error) seems to work for nested vectors.
I have tried in vain to reproduce a method for dispatching on empty vectors in a way equivalent to that for empty tuples.


flav(x::Union{Real, String, Char})=x
flav(v :: AbstractArray)=[flav(v[1])...,(isempty(v[2:end]) ? [] : flav(v[2:end]))...]


v=[1.,'b']
v1=[11,v]
flav(v1)


v2=[[1,"abc"],v1]
v3=[[3,[31,32]],v2]
flav(v3)

v4=[v2,[v1,v3]]

flav(v4)