Scala: построить карту из списка кортежей, но потерпеть неудачу, если есть противоречивые записи

Question

Я думаю, что это может быть обычной операцией.Так что, может быть, это внутри API, но я не могу его найти.Также меня интересует эффективное функциональное / простое решение, если нет.

Учитывая последовательность кортежей ("a" -> 1, "b" ->2, "c" -> 3) Я хочу превратить его в карту.Это легко, используя TraversableOnce.toMap.Но я хочу потерпеть неудачу в этой конструкции, если полученная карта «будет содержать противоречие», то есть разные значения будут присвоены одному и тому же ключу.Как в последовательности ("a" -> 1, "a" -> 2).Но дубликаты должны быть разрешены.

В настоящее время у меня есть этот (очень обязательный) код:

def buildMap[A,B](in: TraversableOnce[(A,B)]): Option[Map[A,B]] = {
  val map = new HashMap[A,B]
  val it = in.toIterator
  var fail = false
  while(it.hasNext){
    val next = it.next()
    val old = map.put(next._1, next._2)
    fail = old.isDefined && old.get != next._2
  }

  if(fail) None else Some(map.toMap)
}

Дополнительный вопрос

Действительно ли необходим финальный toMap?Я получаю сообщение об ошибке при опущении, но я думаю, что это должно работать.Реализация toMap создает новую карту, которую я хочу избежать.

Answer 1

Как всегда при работе с Seq[A], оптимальное решение зависит от типа конкретного бетона. Общим, но не очень эффективным решением было бы сложить на Option[Map[A,B]]:

def optMap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = 
  in.iterator.foldLeft(Option(Map[A,B]())) {
    case (Some(m),e @ (k,v)) if m.getOrElse(k, v) == v => Some(m + e)
    case _ => None
  }

Если вы ограничитесь использованием List[A,B] s, оптимизированная версия будет:

@tailrec
def rmap[A,B](in: List[(A,B)], out: Map[A,B] = Map[A,B]()): Option[Map[A,B]] = in match {
  case (e @ (k,v)) :: tail if out.getOrElse(k,v) == v =>
    rmap(tail, out + e)
  case Nil =>
    Some(out)
  case _ => None
}

Кроме того, может быть реализована менее идиоматическая версия с использованием изменяемых карт:

def mmap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = {
  val dest = collection.mutable.Map[A,B]()

  for (e @ (k,v) <- in) {
    if (dest.getOrElse(k, v) != v) return None
    dest += e
  }

  Some(dest.toMap)
}

Answer 2

Вот медленное отказоустойчивое решение (если создание всей карты, а затем сброс ее, это нормально):

def uniqueMap[A,B](s: Seq[(A,B)]) = {
  val m = s.toMap
  if (m.size == s.length) Some(s) else None
}

Вот изменяемое отказоустойчивое решение (выручить, как только ошибкаобнаружено):

def uniqueMap[A,B](s: Seq[(A,B)]) = {
  val h = new collection.mutable.HashMap[A,B]
  val i = s.iterator.takeWhile(x => !(h contains x._1)).foreach(h += _)
  if (h.size == s.length) Some(h) else None
}

И вот неизменное решение для быстрого отказа:

def uniqueMap[A,B](s: Seq[(A,B)]) = {
  def mapUniquely(i: Iterator[(A,B)], m: Map[A,B]): Option[Map[A,B]] = {
    if (i.hasNext) {
      val j = i.next
      if (m contains j._1) None
      else mapUniquely(i, m + j)
    }
    else Some(m)
  }
  mapUniquely(s.iterator, Map[A,B]())
}

---

Редактировать: и вот решение, использующее put для скорости (надеюсь):

def uniqueMap[A,B](s: Seq[(A,B)]) = {
  val h = new collection.mutable.HashMap[A,B]
  val okay = s.iterator.forall(x => {
    val y = (h put (x._1,x._2))
    y.isEmpty || y.get == x._2 
  })
  if (okay) Some(h) else None
}

Редактировать: теперь протестировано, и оно примерно в 2 раза быстрее при вводе, которое работает (возвращает true), чем Мориц или мое простое решение.

Answer 3

Вы также можете использовать gourpBy следующим образом:

  val pList = List(1 -> "a", 1 -> "b", 2 -> "c", 3 -> "d")

  def optMap[A,B](in: Iterable[(A,B)]): Option[Map[A,B]] = {
    Option(in.groupBy(_._1).map{case(_, list) => if(list.size > 1) return None else list.head})
  }

  println(optMap(pList))

Эффективность конкурентоспособна по сравнению с вышеуказанными решениями. Фактически, если вы изучите реализацию gourpBy, вы увидите, что она очень похожа на некоторые из предложенных решений.

Answer 4

Scala 2.9 уже близко, так почему бы не воспользоваться преимуществом метода комбинаций (вдохновленный ответом Морица):

def optMap[A,B](in: List[(A,B)]) = {
  if (in.combinations(2).exists { 
    case List((a,b),(c,d)) => a == c && b != d
    case _ => false 
  }) None else Some(in.toMap)
}

scala> val in = List(1->1,2->3,3->4,4->5,2->3)
in: List[(Int, Int)] = List((1,1), (2,3), (3,4), (4,5), (2,3))

scala> optMap(in)
res29: Option[scala.collection.immutable.Map[Int,Int]] = Some(Map(1 -> 1, 2 -> 3, 3 -> 4, 4 -> 5))

scala> val in = List(1->1,2->3,3->4,4->5,2->3,1->2)
in: List[(Int, Int)] = List((1,1), (2,3), (3,4), (4,5), (2,3), (1,2))

scala> optMap(in)
res30: Option[scala.collection.immutable.Map[Int,Int]] = None