Use monoids to compute a frequency map of words

Question

I am learning the book functional programming in scala. chapter 10, exercise 20, to implement the following method:

def frequencyMap(strings: IndexedSeq[String]): Map[String, Int]

honestly, I don't have a solution, so, I checked the answer from GIT:

 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))
    }
}

 def bag[A](as: IndexedSeq[A]): Map[A, Int] =
   foldMapV(as, mapMergeMonoid[A, Int](intAddition))((a: A) => Map(a -> 1))
 def frequencyMap(strings: IndexedSeq[String]): Map[String, Int] = bag(strings)

But, when I tried to run a test, I got wrong answer:

frequencyMap(Vector("a rose", "is a", "rose is", "a rose"))

the answer printed:

Map(a rose -> 1)

the expected result:

Map(a -> 3, rose -> 3, is -> 2)

I can't figure out where is wrong with the implementation. could someone explain it for me? thanks.

Edit after the correct answer, and update with a correct implementation

 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))
    //
    val c = for {
      (ka, va) <- a
      (kb, vb) <- b
      if (ka == kb)
    } yield (ka -> V.op(va, vb))

    a ++ b ++ c
  }
}

def bag[A](as: IndexedSeq[A]): Map[A, Int] =
    foldMapV(as, mapMergeMonoid[A, Int](intAddition))((a: A) => Map(a -> 1))
def frequencyMap(strings: IndexedSeq[String]): Map[String, Int] = bag(strings.map(_.split("\\s+")).flatten)

Answer 1

I don't have the book, but following the code from here, I can point out a few things for you to think about( based on some println()s in a REPL session ):

• As S.R.I pointed out, you have a list of phrases, not words. The functions on github don't do anything to separate the word groups for you, so at best, your current input Vector could get:

  Map(a rose -> 2, is a -> 1, rose is -> 1)
  

  You could create a list of words by doing the following to your Vector:

  Vector("a rose", "is a", "rose is", "a rose") map( _.split( " " ).toSeq ) flatten
  

• The mapMergeMonoid function only appears to add the value of k and v together when there keys(k) are the same. Meaning an unsorted list is going to result in a lot of Map(string -> 1).

  You could sort the Vector of words by making the following changes to Vector:

  (Vector("a rose", "is a", "rose is", "a rose") map( _.split( " " ).toSeq ) flatten) sortWith(_.compareTo(_) < 0) 
  

• While foldMapV does split out all the phrases or words from the Vector in a Map[String, Int], it only appears to return the leftmost desired merge for a sorted IndexedSeq. With a sorted Vector of words as I've indicated, I got the result Map(a -> 3) from your implementation of frequencyMap. I would be inclined to use something other than foldMapV though or modify it to make frequencyMap work. The bit that appears to be missing to me is an accumulation of the results of the function it's applying into one large Map. I would also try a more "standard" head/tail recursion than the splitAt() calls(as I'm not convinced the foldMapV was handling is and rose very well).