Adding polynomials represented as maps I'm using maps to represent a polynomial.
The key is the exponent and the value is the coefficient : Map(exp -&gt; coef)

e.g. 2.5*x^5 + 3.0 is represented by : Map(5 -&gt; 2.5, 0 -&gt; 3.0)

I wrote 3 functions (in Scala) to add such polynomials. Which one is the most elegant ? Do you have another version that is preferable/better ? (Implementations in another language such as Haskell are welcome)

Here is a sample testcase : 

val polynom1 = Map(0 -&gt; 1.0, 1 -&gt; 2.0, 2 -&gt; 1.0)
val polynom2 = Map(0 -&gt; 1.0, 1 -&gt; (-2.0), 2 -&gt; 1.0)
val expectedSum = Map(0 -&gt; 2.0, 1 -&gt; 0.0, 2 -&gt; 2.0)


Here are the implementations :

def addMap1(lhs: Map[Int, Double], rhs: Map[Int, Double]) =
  ((lhs.keys ++ rhs.keys) map { k =&gt;
    (k, lhs.getOrElse(k, 0.0) + rhs.getOrElse(k, 0.0))
  }).toMap



def addMap2(lhs: Map[Int, Double], rhs: Map[Int, Double]) = {
    def adjust(kv: (Int, Double)) = {
      val (exp, coef) = kv
      (exp, coef + lhs.getOrElse(exp, 0.0))
    }
    lhs ++ (rhs map adjust)
  }



def addMap3(lhs: Map[Int, Double], rhs: Map[Int, Double]) = {
    def addTerms(acc: Map[Int, Double], x: (Int, Double)) = {
      val (exp, coef) = x
      acc + (exp -&gt; (coef + rhs.getOrElse(exp, 0.0)))
    }
    (lhs foldLeft rhs)(addTerms)
  }
I think that the second implementation of the function is the most readable and concise. There is just the name of def adjust that should be changed. adjust is too vague, sumCoeffs would be more concrete.

It's probably a matter of taste, but the first implementation seems to contain too much nesting (parenthesis and braces). The third implementation looks also a bit more complex than the second, mostly due to the mechanism of foldLeft.

By the way, I've got two suggestions that may slightly improve this code.


Omitting dots for function calls and parenthesis for arguments are not among the recommendations of the official Scala style guide (sections Arity-0 and Arity-1). This practice can reduce the readability. For example, I find that rhs.map(adjust) and lhs.foldLeft(rhs)(addTerms) are easier to perceive for a human-shaped reader than the respective expressions in the original code.
There are several occurrences of getOrElse(exp, 0.0) that can be extracted in a small helper function like private def coefFor(exp : Int, polynoms : Map[Int, Double]) = polynoms.getOrElse(exp, 0.0). This will allow to transform the respective instructions into more elegant, for example: (exp, coef + coefFor(exp, lhs)). But since among the three functions only one will be chosen/used, this will eliminate the duplications and the relevance of this remark.