2

继续使用Scala中的函数式编程，下一个练习是：

implement a bag in Scala

一个包包含一个 Map，其中每个键都等于元素的值，键的值是它在 Vector 中出现的次数。

bag(Vector("good", "dog", "good"))=Map("good"-> 2, "dog" -> 1)

考虑mapMergeMonoid：

// @author - pchiusano
def mapMergeMonoid[K,V](V: Monoid[V]): Monoid[Map[K,V]] =
    new Monoid[Map[K, V]] {
        def zero = Map()
        def op(a: Map[K, V], b: Map[K, V]) = 
            a.map {
                case (k, v) => (k, V.op(v, b.get(k).getOrElse(V.zero) ))
            }
    }

考虑我的实现bagWithMonoids：

def bagWithMonoids[A](as: IndexedSeq[A]): Map[A, Int] = {
    val bagMonoid: Monoid[Map[A, Int]] = mapMergeMonoid(intAddition)
    as.map(x => Map(x -> 1)).foldLeft(bagMonoid.zero)
                 ((acc, elem) => acc ++ bagMonoid.op(elem, acc))
}

为了使它更干净一点，我想(B, A) => B将 foldLeft 的部分替换为bagMonoid.op. 但是，当我这样做时，结果是Map().

我相信这是因为使用该参数bagMonoid.op(acc, elem)会导致 ，这将导致Map()因为acc是一个空地图。

如何清理我的实现以bagMonoid.op用作 foldLeft 的第二个参数？

4

2 回答 2

3

的这种实现mapMergeMonoid偏向于第一个Map参数，这基本上意味着在b但不在的键a永远不会出现在最终结果中。这样做的结果是您的初始累加器必须将IndexedSeq. 那就是as.map(x => x -> 0).toMap下面的部分：

def bag[A](as: IndexedSeq[A]): Map[A, Int] = {
  val bagMonoid: Monoid[Map[A, Int]] = mapMergeMonoid(intAddition)
  as.map(x => Map(x -> 1)).foldLeft(as.map(x => x -> 0).toMap)(bagMonoid.op)
}

zero不再需要。很遗憾。我希望有一个更优雅的解决方案，但我认为通过mapMergeMonoid. 我们需要一个行为更像union.Set

这是一个可能的（我还没有验证幺半群定律成立）mapMergeMonoid，这将允许对 进行更简洁的定义bag：

def mapMergeMonoid[K,V](V: Monoid[V]): Monoid[Map[K, V]] =
  new Monoid[Map[K, V]] {
    def zero = Map()
    def op(a: Map[K, V], b: Map[K, V]) = {
      val pairs = a.keySet.union(b.keySet).map {
        k => (k, V.op(a.get(k).getOrElse(V.zero), b.get(k).getOrElse(V.zero)))
      }

      pairs.toMap
    }
  }

// Using foldLeft
def bag[A](as: IndexedSeq[A]): Map[A, Int] = {
  val bagMonoid: Monoid[Map[A, Int]] = mapMergeMonoid(intAddition)
  as.map(x => Map(x -> 1)).foldLeft(bagMonoid.zero)(bagMonoid.op)
}

// Using reduceLeft
def bag[A](as: IndexedSeq[A]): Map[A, Int] = {
  val bagMonoid: Monoid[Map[A, Int]] = mapMergeMonoid2(intAddition)
  as.map(x => Map(x -> 1)).reduceLeft(bagMonoid.op)
}
于 2013-11-15T03:05:09.847 回答
1

根据我的阅读mapMergeMonoid，实际上根本不会产生 Monoid。要引用 Scala 中的 FP，幺半群必须具有：

值，零：作为该操作的标识的 A。也就是说，对于任何 x，op(x, zero) == x 和 op(zero, x) == x：A。

但

val intAddition: Monoid[Int] = new Monoid[Int] {
  def op(a: Int, b: Int) = a + b
  def zero = 0
}

val mergeInts = mapMergeMonoid[String,Int](intAddition)

mergeInts.op(mergeInts.zero, Map ("x" -> 1))

产生一个空 Map，即 op(zero, x) = zero

我最终得到：

def mapMergeMonoid[K,V](V: Monoid[V]) =
  new Monoid[Map[K, V]] {
    def zero = Map[K,V]()
    def op(a: Map[K, V], b: Map[K, V]) =
      a.map {
        case (k, v) => (k, V.op(v, b.get(k) getOrElse V.zero))
      } ++ (b -- a.keys)
  }

这似乎表现得更好。然后，您可以使用另一个练习中的 foldMap 将 bag 写为

def bag[A](as: IndexedSeq[A]): Map[A, Int] =
  IndexedSeqFoldable.foldMap(as)(x => Map(x -> 1))(mapMergeMonoid(intAddition))
于 2014-06-24T21:19:31.653 回答