自动散列一致案例类

发布于 2024-12-23 14:42:47 字数 1254 浏览 1 评论 0原文

我正在寻找一种方法,让类的行为就像案例类一样,但会自动 哈希 consed。

对于整数列表实现此目的的一种方法是:

import scala.collection.mutable.{Map=>MutableMap}

sealed abstract class List
class Cons(val head: Int, val tail: List) extends List
case object Nil extends List

object Cons {
  val cache : MutableMap[(Int,List),Cons] = MutableMap.empty
  def apply(head : Int, tail : List) = cache.getOrElse((head,tail), {
    val newCons = new Cons(head, tail)
    cache((head,tail)) = newCons
    newCons
  })
  def unapply(lst : List) : Option[(Int,List)] = {
    if (lst != null && lst.isInstanceOf[Cons]) {
      val asCons = lst.asInstanceOf[Cons]
      Some((asCons.head, asCons.tail))
    } else None
  }
}

并且,例如,当

scala> (5 :: 4 :: scala.Nil) eq (5 :: 4 :: scala.Nil)
resN: Boolean = false

我们

scala> Cons(5, Cons(4, Nil)) eq Cons(5, Cons(4, Nil))
resN: Boolean = true

现在得到时,我正在寻找的是实现此目的的通用方法(或非常类似的方法)。理想情况下,我不想输入太多内容:(

class Cons(val head : Int, val tail : List) extends List with HashConsed2[Int,List]

或类似内容)。有人可以想出一些类型系统巫术来帮助我,还是我必须等待宏语言可用?

I'm looking for a way to have classes that behave just like case classes, but that are automatically hash consed.

One way to achieve this for integer lists would be:

import scala.collection.mutable.{Map=>MutableMap}

sealed abstract class List
class Cons(val head: Int, val tail: List) extends List
case object Nil extends List

object Cons {
  val cache : MutableMap[(Int,List),Cons] = MutableMap.empty
  def apply(head : Int, tail : List) = cache.getOrElse((head,tail), {
    val newCons = new Cons(head, tail)
    cache((head,tail)) = newCons
    newCons
  })
  def unapply(lst : List) : Option[(Int,List)] = {
    if (lst != null && lst.isInstanceOf[Cons]) {
      val asCons = lst.asInstanceOf[Cons]
      Some((asCons.head, asCons.tail))
    } else None
  }
}

And, for instance, while

scala> (5 :: 4 :: scala.Nil) eq (5 :: 4 :: scala.Nil)
resN: Boolean = false

we get

scala> Cons(5, Cons(4, Nil)) eq Cons(5, Cons(4, Nil))
resN: Boolean = true

Now what I'm looking for is a generic way to achieve this (or something very similar). Ideally, I don't want to have to type much more than:

class Cons(val head : Int, val tail : List) extends List with HashConsed2[Int,List]

(or similar). Can someone come up with some type system voodoo to help me, or will I have to wait for the macro language to be available?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

满天都是小星星 2024-12-30 14:42:47

您可以定义一些 InternableN[Arg1, Arg2, ..., ResultType] 特征,其中 N 是 apply() 的参数数量:Internable1[A ,Z]Internable2[A,B,Z] 等。这些特征定义了缓存本身、intern() 方法和 申请我们想要劫持的方法。

我们必须定义一个特征(或抽象类),以确保您的 InternableN 特征确实存在一个需要重写的 apply 方法,我们将其称为 Applyable

trait Applyable1[A, Z] {
  def apply(a: A): Z
}
trait Internable1[A, Z] extends Applyable1[A, Z] {
  private[this] val cache = WeakHashMap[(A), Z]()
  private[this] def intern(args: (A))(builder: => Z) = {
    cache.getOrElse(args, {
      val newObj = builder
      cache(args) = newObj
      newObj
    })
  }
  abstract override def apply(arg: A) = {
    println("Internable1: hijacking apply")
    intern(arg) { super.apply(arg) }
  }
}

类的伴生对象必须是实现 ApplyableNInternableN 的具体类的混合。在伴生对象中直接定义 apply 是行不通的。

// class with one apply arg 
abstract class SomeClassCompanion extends Applyable1[Int, SomeClass] {
  def apply(value: Int): SomeClass = {
    println("original apply")
    new SomeClass(value)
  }
}
class SomeClass(val value: Int)
object SomeClass extends SomeClassCompanion with Internable1[Int, SomeClass]

这样做的一个好处是,不需要修改原始申请来适应实习。它只创建实例,并且仅在需要创建实例时调用。

整件事也可以(并且应该)为具有多个参数的类定义。对于两个参数的情况:

trait Applyable2[A, B, Z] {
  def apply(a: A, b: B): Z
}
trait Internable2[A, B, Z] extends Applyable2[A, B, Z] {
  private[this] val cache = WeakHashMap[(A, B), Z]()
  private[this] def intern(args: (A, B))(builder: => Z) = {
    cache.getOrElse(args, {
      val newObj = builder
      cache(args) = newObj
      newObj
    })
  }
  abstract override def apply(a: A, b: B) = {
    println("Internable2: hijacking apply")
    intern((a, b)) { super.apply(a, b) }
  }
}

// class with two apply arg 
abstract class AnotherClassCompanion extends Applyable2[String, String, AnotherClass] {
  def apply(one: String, two: String): AnotherClass = {
    println("original apply")
    new AnotherClass(one, two)
  }
}
class AnotherClass(val one: String, val two: String)
object AnotherClass extends AnotherClassCompanion with Internable2[String, String, AnotherClass]

交互显示 Internables 的 apply 方法先于原始 apply() 执行,后者仅在需要时执行。

scala> import SomeClass._
import SomeClass._

scala> SomeClass(1)
Internable1: hijacking apply
original apply
res0: SomeClass = SomeClass@2e239525

scala> import AnotherClass._
import AnotherClass._

scala> AnotherClass("earthling", "greetings")
Internable2: hijacking apply
original apply
res1: AnotherClass = AnotherClass@329b5c95

scala> AnotherClass("earthling", "greetings")
Internable2: hijacking apply
res2: AnotherClass = AnotherClass@329b5c95

我选择使用 Wea​​kHashMap,这样一旦在其他地方不再引用它们,驻留缓存就不会阻止对驻留实例进行垃圾回收。

代码作为 Github 要点整齐地提供。

You can define a few InternableN[Arg1, Arg2, ..., ResultType] traits for N being the number of arguments to apply(): Internable1[A,Z], Internable2[A,B,Z], etc. These traits define the cache itself, the intern() method and the apply method we want to hijack.

We'll have to define a trait (or an abstract class) to assure your InternableN traits that there is indeed an apply method to be overriden, let's call it Applyable.

trait Applyable1[A, Z] {
  def apply(a: A): Z
}
trait Internable1[A, Z] extends Applyable1[A, Z] {
  private[this] val cache = WeakHashMap[(A), Z]()
  private[this] def intern(args: (A))(builder: => Z) = {
    cache.getOrElse(args, {
      val newObj = builder
      cache(args) = newObj
      newObj
    })
  }
  abstract override def apply(arg: A) = {
    println("Internable1: hijacking apply")
    intern(arg) { super.apply(arg) }
  }
}

The companion object of your class will have to be a mixin of a concrete class implementing ApplyableN with InternableN. It would not work to have apply directly defined in your companion object.

// class with one apply arg 
abstract class SomeClassCompanion extends Applyable1[Int, SomeClass] {
  def apply(value: Int): SomeClass = {
    println("original apply")
    new SomeClass(value)
  }
}
class SomeClass(val value: Int)
object SomeClass extends SomeClassCompanion with Internable1[Int, SomeClass]

One good thing about this is that the original apply need not be modified to cater for interning. It only creates instances and is only called when they need to be created.

The whole thing can (and should) also be defined for classes with more than one argument. For the two-argument case:

trait Applyable2[A, B, Z] {
  def apply(a: A, b: B): Z
}
trait Internable2[A, B, Z] extends Applyable2[A, B, Z] {
  private[this] val cache = WeakHashMap[(A, B), Z]()
  private[this] def intern(args: (A, B))(builder: => Z) = {
    cache.getOrElse(args, {
      val newObj = builder
      cache(args) = newObj
      newObj
    })
  }
  abstract override def apply(a: A, b: B) = {
    println("Internable2: hijacking apply")
    intern((a, b)) { super.apply(a, b) }
  }
}

// class with two apply arg 
abstract class AnotherClassCompanion extends Applyable2[String, String, AnotherClass] {
  def apply(one: String, two: String): AnotherClass = {
    println("original apply")
    new AnotherClass(one, two)
  }
}
class AnotherClass(val one: String, val two: String)
object AnotherClass extends AnotherClassCompanion with Internable2[String, String, AnotherClass]

The interaction shows that the Internables' apply method executes prior to the original apply() which gets executed only if needed.

scala> import SomeClass._
import SomeClass._

scala> SomeClass(1)
Internable1: hijacking apply
original apply
res0: SomeClass = SomeClass@2e239525

scala> import AnotherClass._
import AnotherClass._

scala> AnotherClass("earthling", "greetings")
Internable2: hijacking apply
original apply
res1: AnotherClass = AnotherClass@329b5c95

scala> AnotherClass("earthling", "greetings")
Internable2: hijacking apply
res2: AnotherClass = AnotherClass@329b5c95

I chose to use a WeakHashMap so that the interning cache does not prevent garbage collection of interned instances once they're no longer referenced elsewhere.

Code neatly available as a Github gist.

○愚か者の日 2024-12-30 14:42:47

也许有点 hacky,但您可以尝试定义自己的 intern() 方法,就像 Java 的 String 一样:

import scala.collection.mutable.{Map=>MutableMap}

object HashConsed {
  val cache: MutableMap[(Class[_],Int), HashConsed] = MutableMap.empty
}

trait HashConsed {
  def intern(): HashConsed = 
    HashConsed.cache.getOrElse((getClass, hashCode), {
      HashConsed.cache((getClass, hashCode)) = this
      this
    })
}

case class Foo(bar: Int, baz: String) extends HashConsed

val foo1 = Foo(1, "one").intern()
val foo2 = Foo(1, "one").intern()

println(foo1 == foo2) // true
println(foo1 eq foo2) // true

Maybe a little hacky, but you could try defining your own intern() method, like Java's String has:

import scala.collection.mutable.{Map=>MutableMap}

object HashConsed {
  val cache: MutableMap[(Class[_],Int), HashConsed] = MutableMap.empty
}

trait HashConsed {
  def intern(): HashConsed = 
    HashConsed.cache.getOrElse((getClass, hashCode), {
      HashConsed.cache((getClass, hashCode)) = this
      this
    })
}

case class Foo(bar: Int, baz: String) extends HashConsed

val foo1 = Foo(1, "one").intern()
val foo2 = Foo(1, "one").intern()

println(foo1 == foo2) // true
println(foo1 eq foo2) // true
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文