title: How to deep merge two multi-root tree structure made of array and hashes
body: <p>I have a nested structure made of <code>Hash</code>es and <code>Array</code>s that we can call multi-root nth-ary Tree.</p>
  
  <p>I'm representing this structure</p>
  
  <p>Here's an example:</p>
  
  <pre><code>[:o, {
    a: :b,
    c: [:d, :e, { f: { h: :i, l: [:m, :n] } }]
  }]
  </code></pre>
  
  <p>That represents can be represented with this schema:</p>
  
  <pre><code>o        a          c
          /          /|\
         b          d e f
                        /\
                       h  l
                      /  / \
                     i  m   n
  </code></pre>
  
  <p>I want to deep merge it with another similar structure. Here's an example:</p>
  
  <pre><code>[:z, {
    o: :s,
    c: [:f, { d: :w }]
  }]
  
  z      o      c
         |     / \
         s    f   d
                   \
                    w
  </code></pre>
  
  <p>The resulting tree should be something like this:</p>
  
  <pre><code>[:z, {
      a: :b,
      c: [:e, { f: { h: :i, l: [:m, :n] }, d: :w }],
      o: :s
   }]
  
  
  z       a           c           o
          |          /|\          |
          b         e f d         s
                     /|  \
                    h l   w
                    | |\
                    i m n
  </code></pre>
  
  <p>How can I do this?</p>
  
  <p>I started with this, but I got struck:</p>
  
  <pre><code>def deep_merge(a, b)
    case a
    when Hash
      case b
      when Hash
        merge_hashes(a, b)
      when Array
        merge_array_hash(b, a)
      else
        [b, a]
      end
    when Array
      case b
      when Array
        merge_arrays(a, b)
      when Hash
        merge_array_hash(a, b)
      else
        [b] + a
      end
    else
      case b
      when Hash
        [a, b]
      when Array
        [a] + b
      else
        a == b ? a : [a, b]
      end
    end
  end
  
  # EXAMPLES:
  # merge_array_hash([:a, :b], { f: :w })
  # =&gt; [:a, :b, { f: :w }]
  # merge_array_hash([:a, :b, { c: :d }], { f: :w })
  # =&gt; [:a, :b, { c: :d, f: :w }]
  def merge_array_hash(a, b)
    if a.last.is_a? Hash
      a[0...-1] + [merge_hashes(a.last, b)]
    else
      a + [b]
    end
  end
  
  # EXAMPLES:
  # merge_hashes({ a: :b }, { c: :d })
  # =&gt; { a: :b, c: :d }
  # merge_hashes({ a: :b }, { d: e, a: :f })
  # =&gt; { a: [:b, :f], d: :e }
  def merge_hashes(a, b)
    a.deep_merge(b) do |_, this_val, other_val|
      deep_merge(this_val, other_val)
    end
  end
  
  # EXAMPLES:
  # merge_arrays([:a, :b], [:c])
  # =&gt; [:a, :b, :c]
  # merge_arrays([:a, :b { c: :d }], [:f, { c: :e }])
  # =&gt; [:a, :b, :f, { c: [:d, :e] }]
  # merge_arrays([:a, :b { c: :d }], [:f, { c: :e }])
  # =&gt; [:a, :b, :f, { c: [:d, :e] }]
  def merge_arrays(a, b)
    keys = merge_array_keys(a, b)
    hashes = merge_hashes(a.last.is_a?(Hash) ? a.last : {}, b.last.is_a?(Hash) ? a.last : {})
    hashes.empty? keys : (keys + [hashes])
  end
  
  # EXAMPLES:
  # merge_array_keys([:a, :b], [:f])
  # =&gt; [:a, :b, :f]
  # merge_array_keys([:a, :b { c: :d }], [:f, { c: :e }])
  # =&gt; [:a, :b, :f]
  def merge_array_keys(a, b)
    a.reject { |e| e.is_a?(Hash) } + b.reject { |e| e.is_a?(Hash) }
  end
  </code></pre>
  
  <p>As you can see, my solution was a little bit too complex, I think there's a more intelligent way, but I can't find it. Any ideas?</p>
  
  <p>NB: the key order doesn't metter</p>
  
  <p>NB: If there is an Array that contains an Hash, the hash must be the last item of the array</p>
  
  <p>NB: I'm not interested in performances, it could be also very slow for big trees</p>
  
  <p>NB: If you have better ideas to represent this structure in a more intelligent way, for me is ok!</p>