title: Generic diff for complex hierarchical data structure
body: <p>I have a complex data structure consisting of case classes, maps and sets. I would like to know if there is a <em>generic</em> mechanism to calculate a "diff" between two structures.</p>
  
  <p>As a simple example:</p>
  
  <pre><code>val s0 = Set(1,2,3)
  val s1 = Set(2,3,4)
  val diff = diff(s0, s1)
  // this should contain the information that 1 has been removed and 4 has
  // been added
  assert(s1 == diff.patch(s0))
  </code></pre>
  
  <p>A somewhat more complex example:</p>
  
  <pre><code>case class User(name: String, roles: Set[String])
  val user0 = User("Hans", Set("Developer", "Admin")
  val user1 = User("Hans", Set("Admin", "Manager")
  val diff = diff(user0, user1)
  // this should contain the information that "Developer" has been removed
  // and "Manager" has been added to the roles field
  </code></pre>
  
  <p>Note that I am interested in a <strong>generic</strong> solution that works for arbitrary case classes and deep hierarchies. I have a feeling that this should be possible using a typeclass-based approach and either shapeless or some boilerplate. Bonus points for an approach that allows specifying the "diff algorithm" for new collection types.</p>
  
  <p>I have found <a href="https://github.com/stacycurl/delta" rel="nofollow">https://github.com/stacycurl/delta</a> . This seems to be pretty close to what I am looking for. But I don't really understand it.</p>