CODEWITHSUNDEEP
scala
JasonMond
JasonMond

Reputation: 1450

Scala foldLeft adding one more element?

I'm trying to create a fly-by-seat-of-pants sparse vector library in scala and I'm hitting an issue with foldLeft where it seems to be creating or adding an extra element on sequences of length one.

Here's my sparse addition function:

  def addTwoMaps(m1: Map[Int,Double], m2: Map[Int,Double]) =
  m1 ++ m2.map{ case (k,v) => k -> (v + m2.getOrElse(k, 0.)) }

And here's my "add over sequence of maps/sparse vectors and normalize" function:

def addNMaps(ms : Map[Int, Double]*) = {
val denom = if (ms.length > 0) ms.length.toDouble else 1
ms.foldLeft(Map.empty[Int, Double])((a,b) => addTwoMaps(a,b)).mapValues(_ / denom)
}

(for my particular case, the values of each input map sum to one so all I have to do is divide by the length of the argument sequence to make sure the resulting map sums to one over its values)

As a test case, if I add two maps which have values that sum to one, it works out fine:

scala> Common.addNMaps(Map(1->1), Map(1->1))
res34: scala.collection.immutable.Map[Int,Double] = Map(1 -> 1.0)

But if I have only one argument:

scala> Common.addNMaps(Map(1->1))
res33: scala.collection.immutable.Map[Int,Double] = Map(1 -> 2.0)

The values sum to two all of a sudden! My guess is that the single Map(1->1) is being added twice somehow in foldLeft but it's only a guess.

What am I doing wrong? And how can I get Common.addNMaps(Map(1->1)) to return Map(1->1.0)?

Upvotes: 1

Views: 757

Answers (1)

Travis Brown
Travis Brown

Reputation: 139038

There's a typo in your addTwoMaps, which should be:

def addTwoMaps(m1: Map[Int,Double], m2: Map[Int,Double]) =
  m1 ++ m2.map{ case (k,v) => k -> (v + m1.getOrElse(k, 0.)) }

You need to call getOrElse on m1, not m2.

Note that in this case you can use an IntMap, which has a handy unionWith method (presumably inspired by Haskell's Data.Map.unionWith):

import scala.collection.immutable.IntMap

def addNMaps(ms : IntMap[Double]*) = {
  val denom = if (ms.length > 0) ms.length else 1
   ms.foldLeft(IntMap.empty[Double]) {
     (a, b) => a.unionWith(b, (_, x, y) => x + y)
   }.mapValues(_ / denom)
 }

I'm not sure why unionWith isn't part of the standard Scala Map API.

Upvotes: 1

Related Questions