Add TotalHashMap

[TomasMikula]

A total map is a map that is defined everywhere.

For this data structure, we only consider a special kind of total maps: the ones that are non-zero at at most a finite number of points. TotalHashMap can then be implemented using an ordinary HashMap for keys with non-zero values, and assume zero everywhere else.

EDIT: by "zero" I mean any constant value, not necessarily related to any algebraic notion of zero. So a better phrasing would be that we consider total maps that are constant except for at most a finite number of points.

[non]

Would you consider a more general TotalMap that can have any value as the default value? With that, we could define a one as well as zero element, and support a complete boolean algebra. This could also enable a .mapValues method to behave more predictably.

It's also possible that this should be a separate data structure.

[TomasMikula]

Would you consider a more general TotalMap that can have any value as the default value?

I was not clear enough, but that's what I meant. By "zero" I meant whatever default value, not related to a zero in any algebraic structure.

With that, we could define a one as well as zero element, and support a complete boolean algebra.

For that, you would need an extra bit of information to indicate whether the default value is a zero or one, right? That extra bit would mean a separate data structure.

Then still, you couldn't have both an infinite number of zeros and an infinite number of ones at the same time. Although this property seems to be preserved under the operations of a Boolean algebra.

[non]

Yes, I had been imagining something like this:

package he

class TotalMap[K, V](private[he] val m: Map[K, V], private[he] val d: V) {
  def apply(k: K): V =
    m.getOrElse(k, d)
  def updated(k: K, v: V): TotalMap[K, V] =
    new TotalMap(m.updated(k, v), d)
  def compress(implicit e: Eq[V]): TotalMap[K, V] =
    m.filter { case (_, v) => v =!= d }
  def map[W](f: V => W): TotalMap[K, W] =
    new TotalMap(m.map { case (k, v) => f(v) }, f(d))
}

object TotalMap {

  def constant[K, V](v: V): TotalMap[K, V] =
    new TotalMap(Map.empty[K, V], v)

  implicit def totalMapRig[K, V: Rig]: Rig[TotalMap[K, V]] =
    new TotalMap[K, V] {
      def zero: TotalMap[K, V] = constant(Rig[V].zero)
      def one: TotalMap[K, V] = constant(Rig[V].one)
      def plus(x: TotalMap[K, V], y: TotalMap[K, V]): TotalMap[K, V] = {
        val e = constant[K, V](x.d + yd)
        (x.m.keys | y.m.keys).foldLeft(e)((m, k) => m.updated(k, x(k) + y(k)))
      }
      def times(x: TotalMap[K, V], y: TotalMap[K, V]): TotalMap[K, V] = {
        val e = constant[K, V](x.d * yd)
        (x.m.keys | y.m.keys).foldLeft(e)((m, k) => m.updated(k, x(k) * y(k)))
      }
    }

  implicit def totalMapEq[K, V: Eq]: Eq[TotalMap[K, V]] =
    new Eq[TotalMap[K, V]] {
      def eqv(x: TotalMap[K, V], y: TotalMap[K, V]): Boolean =
        x.d === y.d &&
          x.m.forall { case (k, v) => v == y(k) } &&
          y.m.forall { case (k, v) => v == x(k) }
    }
}

In fact once you have this structure you can go on to define a Ring as well. To me part of the appeal of this structure is that it gives you the kind of getOrElse operation that many people want built-in. One downside with using a type class for the default value is that it may tempt users to define semi-bogus type class instances just for the default behavior.

[non]

(This is just a sketch -- in practice I'd probably want to remove the .compress method and just require Eq[V] instances on some of the other methods. If I can't ensure that m is compressed, then it makes implementing something like .hashCode hard or impossible.)

[TomasMikula]

Ah, right, no extra bit needed and no need to restrict the default element
to zero or one (though if we start with just zero/one defaults, this will
be preserved under boolean operations). It can be a full boolean algebra!

On Sep 15, 2016 12:25 PM, "Erik Osheim" [email protected] wrote:

(This is just a sketch -- in practice I'd probably want to remove the
.compress method and just require Eq[V] instances on some of the other
methods. If I can't ensure that m is compressed, then it makes
implementing something like .hashCode hard or impossible.)

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#8 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAadH0452JPu263qZakPYNzy0ru5H5r9ks5qqXFcgaJpZM4J9FDV
.