Adding polynomials represented as maps

Question

I'm using maps to represent a polynomial. The key is the exponent and the value is the coefficient : Map(exp -> coef)

e.g. 2.5*x^5 + 3.0 is represented by : Map(5 -> 2.5, 0 -> 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 -> 1.0, 1 -> 2.0, 2 -> 1.0)
val polynom2 = Map(0 -> 1.0, 1 -> (-2.0), 2 -> 1.0)
val expectedSum = Map(0 -> 2.0, 1 -> 0.0, 2 -> 2.0)

Here are the implementations :

def addMap1(lhs: Map[Int, Double], rhs: Map[Int, Double]) =
  ((lhs.keys ++ rhs.keys) map { k =>
    (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 -> (coef + rhs.getOrElse(exp, 0.0)))
    }
    (lhs foldLeft rhs)(addTerms)
  }

Antot · Accepted Answer · 2016-01-10 14:08:30Z

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.

Another alternative to repeated use of getOrElse would be to create the map with a chained call to .withDefaultValue — Morgen
– Morgen, Commented Jan 15, 2016 at 3:01

Peter Neyens · Accepted Answer · 2016-01-12 20:15:25Z

A more functional way would be to use a monoid type class.

A monoid in short has two operations :

empty / zero / identity
append

A simple example is a monoid for integer addition: 0 as the empty/neutral element and + as the append operation.

There are a few libraries in Scala (like Scalaz, Cats/Spire) which define Monoid and contain monoid instances for types such as Int, Map, ...

The only problem in your case is that a lawfull monoid for Double cannot be defined (because of its hardware representation).

Since you were already planning to use Double, you could use an unlawful monoid instance for Double.

Using scalaz and scalaz-outlaws as an example, this then could look like :

import scalaz.syntax.monoid._        // use |+| syntax
import scalaz.std.map._              // get monoid instance for Map
import scalaz.std.anyVal._           // get monoid instance for Int
import scalaz.outlaws.std.double._   // get monoid instance for Double 

polynom1 |+| polynom2

You could also give Spire a closer look, which includes Real (which can store real numbers in any desired precision and has a lawful monoid) and Polynomial.

Thank you for you answer (+1) ! I wasn't aware that such type class existed. Is there no "ring" or "group" type class ? I suppose that it would be even better... — Julien__
– Julien__, Commented Jan 19, 2016 at 0:02
You should give Spire a closer look, it has type classes for Ring and also for Semigroup (which has the |+| append operation but no empty element). — Peter Neyens
– Peter Neyens, Commented Jan 19, 2016 at 17:44

Stack Exchange Network

Adding polynomials represented as maps

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Adding polynomials represented as maps

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions