Cross-encoding list hashing inspired by objecthash

listhash.scala

package listhash

enum Expr:
  case Atom(value: Array[Byte] | String | Symbol) extends Expr
  case Comp(value: List[Expr]) extends Expr

opaque type ListHash = Array[Byte]

/** Inspired by https://github.com/benlaurie/objecthash */
def listHash: Expr => ListHash =
  case Expr.Atom(a: Array[Byte]) => hash('b', a)
  case Expr.Atom(a: String) => hash('t', encode(a))
  case Expr.Atom(a: Symbol) => hash('s', encode(a.name))
  case Expr.Comp(Nil) => hash('n')
  case Expr.Comp(h :: t) => hash('p', listHash(h), listHash(Expr.Comp(t)))

/** Concatenates all input bytes and creates a SHA-256 hash */
private def hash(tag: Byte, values: Array[Byte]*) =
  val d = java.security.MessageDigest.getInstance("SHA-256")
  d.update(tag)
  for (v <- values) d.update(v)
  d.digest()

private def encode(s: String) = s.getBytes("UTF-8")

@main def demo =
  println(listHash(Expr.Comp(List.empty)))
  println(listHash(Expr.Atom(Symbol("hello"))))