Реализуйте коллекцию scala, чтобы карта, фильтр и т. Д. Создавали правильный тип

Question

Я пытаюсь реализовать карту со значением по умолчанию , и мне бы хотелось, чтобы фильтры, карты и т. Д. Вместо DefaultingMap также создавали DefaultingMap, когда это возможно. Вот моя первоначальная реализация:

class DefaultingMap[K, V](defaultValue: => V)
extends mutable.HashMap[K, V]
with mutable.MapLike[K, V, DefaultingMap[K, V]] {

  override def empty = new DefaultingMap[K, V](defaultValue)

  override def default(key: K): V = {                 
    val result = this.defaultValue
    this(key) = result
    result                                            
  }
}

Я получаю объекты типа DefaultingMap, когда я использую filter, но не когда я использую map:

scala> val counter = new DefaultingMap[Char, Int](0)
counter: DefaultingMap[Char,Int] = Map()

scala> for (c <- "ababcbbb") counter(c) += 1

scala> counter.filter{case (k, v) => v > 1}
res1: DefaultingMap[Char,Int] = Map((a,2), (b,5))

scala> counter.map{case (k, v) => (k, v * 2)}
res2: scala.collection.mutable.HashMap[Char,Int] = Map((a,4), (c,2), (b,10))

Разница между этими двумя методами заключается в том, что map принимает неявное CanBuildFrom. Итак, я понял, что мне нужно где-то implicit def, чтобы предоставить CanBuildFrom. Моей первой интуицией было сделать то, что сделано в HashMap:

object DefaultingMap extends generic.MutableMapFactory[DefaultingMap] {

  def empty[K, V]: DefaultingMap[K, V] = // Not possible!

  implicit def canBuildFrom[K, V]:
    generic.CanBuildFrom[Coll, (K, V), DefaultingMap[K, V]] = 
      new MapCanBuildFrom[K, V]
}

Я полагаю, что это скомпилирует его, но этот подход не сработает, потому что невозможно определить метод empty - вам нужно знать, каким должен быть defaultValue. Если бы я мог определить CanBuildFrom в самом классе вместо объекта-компаньона, я был бы в порядке, потому что defaultValue доступен там.

Как мне заставить это работать?

Answer 1

Изменяемые карты - это Builder s в Scala, поэтому MapFactory по умолчанию использует пустую карту рассматриваемого типа для получения компоновщика.

Если у вас есть пользовательские правила построения карты, вы можете определить собственную фабрику, аналогичную collection.generic.MapFactory. Вам нужно будет определить его аналогичным образом, как здесь, но заставить метод empty и метод newBuilder принять дополнительный аргумент для defaultValue.

Что-то вроде (если вы прочитаете больше об API коллекций Scala 2.8 в другой предложенной ссылке, вы обнаружите, что вам не нужно реализовывать общие сопутствующие объекты для карт):

import collection._                                                                      


class DefaultingMap[K, V](val defaultValue: V)                                                                      
extends mutable.HashMap[K, V]                                                                                       
with mutable.MapLike[K, V, DefaultingMap[K, V]] {                                                                   

  override def empty = new DefaultingMap(defaultValue)                                                              

}                                                                                                                   


object DefaultingMap {                                                                                              
  def newBuilder[K, V](d: V): DefaultingMap[K, V] = new DefaultingMap[K, V](d)                                      

  implicit def canBuildFrom[K, V] =                                                                                 
    new generic.CanBuildFrom[DefaultingMap[K, V], (K, V), DefaultingMap[K, V]] {                                    
      def apply(from: DefaultingMap[K, V]) = newBuilder[K, V](from.defaultValue)                                    
      def apply() = error("unsupported default apply")                                                              
    }                                                                                                               
}                                                                                                                   


object Main {                                                                                                       
  def main(args: Array[String]) {                                                                                   
    println((new DefaultingMap[Int, Int](5)).defaultValue)                                                          
    println(((new DefaultingMap[Int, Int](5)).map(x => x)).defaultValue)                                            
  }                                                                                                                 
}

Печать:

$ scalac defaulting.scala
$ scala Main
5
5

Я признаю, что это все еще не решает проблему без параметров apply.

Answer 2

Если вы используете collection.immutable.Map в 2.8 или выше, вам доступен метод withDefault:

val m = collection.immutable.Map(1->"a", 2->"b", 3->"c")
val n = m withDefaultValue "default"

// n(7) will return "default"

ОБНОВЛЕНИЕ

Если вы 'переопределяя коллекцию, переместите withDefaultValue в конец цепочки обработки:

val o = (for ((k, v) <- m) yield (k, v)) withDefaultValue "default"
// o(0) will return "default"

Answer 3

Хорошо, вот подход, который очень, очень близок к тому, что я хочу:

class DefaultingMap[K, V](defaultValue: => V)
extends mutable.HashMap[K, V]
with mutable.MapLike[K, V, DefaultingMap[K, V]] {

  override def empty = new DefaultingMap[K, V](defaultValue)

  override def default(key: K): V = {                 
    val result = this.defaultValue
    this(key) = result
    result                                            
  }

  implicit def canBuildFrom[NK] =
    new generic.CanBuildFrom[DefaultingMap[K, V], (NK, V), DefaultingMap[NK, V]] {
      def apply(from: DefaultingMap[K, V]) =
        new DefaultingMap[NK, V](from.newDefaultValue)
      def apply() =
        new DefaultingMap[NK, V](defaultValue)
    }

  def newDefaultValue = defaultValue
}

Теперь, если я получу это CanBuildFrom в область действия, все будет работать как шарм:

scala> val counter = new DefaultingMap[Char, Int](0)
counter: DefaultingMap[Char,Int] = Map()

scala> for (c <- "ababcbbb") counter(c) += 1

scala> import counter._
import counter._

scala> counter.map{case (k, v) => (k, v * 2)}
res1: DefaultingMap[Char,Int] = Map((a,4), (c,2), (b,10))

scala> for ((k, v) <- counter; if v > 1) yield (k.toString, v * 2)
res2: DefaultingMap[java.lang.String,Int] = Map((a,4), (b,10))

Однако, если я остановлюсь на import counter._, я получу то же поведение, что и раньше. Если я смогу просто выяснить, как найти этот implicit def canBuildFrom, я буду настроен ...

Answer 4

Это не поможет вам с типом возврата map (но, опять же, значение по умолчанию для новой коллекции, как правило, не может быть определено с помощью преобразования map).Но чтобы дать вам другой подход:

class DefaultHashMap[A, B](dflt: => B) extends scala.collection.mutable.Map[A, B] {
  val underlying = new scala.collection.mutable.HashMap[A, B]()

  def get(key: A) = underlying.get(key) orElse Some(default(key))
  def iterator: Iterator[(A, B)] = underlying.iterator
  def +=(kv: (A, B)) = { underlying += kv; this }
  def -=(key: A) = { underlying -= key; this }
  override def empty: DefaultHashMap[A, B] = new DefaultHashMap[A, B](dflt)
  override def default(key: A) = dflt
}

Answer 5

API Scala 2.8 Collections - очень хороший документ, и я, кажется, помню, что он обсуждал этот аспект преобразования, хотя я точно не помню, где. Я думаю, это не очень полезно ...