1
\$\begingroup\$

This is for purely pedagogical purposes only. So, within the contrived data structure and its constraints, I'm interested in knowing how might one improve that reduce function and whether I've properly used the Semigroup typeclass correctly here.

object ComplexData {
  import cats.Semigroup
  import cats.instances.all._

  case class Element(name: String, value: Int, els: List[Element] = Nil) {

  def reduce[A : Semigroup](z: A)(f: Element => A): A = {
      Semigroup[A].combine(f(this),
        els match {
          case Nil => z
          case _ => els.map(_.reduce(z)(f)).reduce((a, b) => Semigroup[A].combine(a, b))
        })
      }
    }

    val e1 = Element("Zero", 0,
      List(
        Element("One", 1,
          List(Element("Two", 2,
            List(
             Element("Three", 3),
             Element("Four", 4))))),
        Element("Five", 5,
          List(
           Element("Six", 6),
           Element("Seven", 7),
           Element("Eight", 8,
             List(
               Element("Nine", 9),
               Element("Ten", 10)))))))

   e1.reduce(0)(_.value) 
   //res0: Int = 55

   e1.reduce("")(_.name + " ") 
   //res1: String = Zero One Two Three...

   e1.reduce(0)(_.els.length) 
   //res2: Int = 10

   e1.reduce("")(e => e.name + " -> " + e.value + ", ")
   //res3: String = One -> 1, Two -> 2, Three -> 3, ...
 }

Specifically:

  1. While it works, not excited by the use of view bounds given that they are long since deprecated (attempting to use A <: Semigroup[A]in the function signature did not compile), do I really need an implicit definition here of the semigroup if I wanted to go this way?
  2. That pattern match seems accidentally complex, even given my constraints there's probably a more elegant or at least more straightforward way to do that, yes?
  3. If I used aMonoid[A]instead of a semigroup I could get rid of thezparameter and provide aZero[A]orEmpty[A], I think - is that the preferred way to go?
\$\endgroup\$
  • 1
    \$\begingroup\$ Hi, you flagged your own question to migrate to Stack Overflow. I think it's better here. \$\endgroup\$ – janos Jan 2 '18 at 18:54
1
\$\begingroup\$

Yes, using a Monoid can simplify what you want:

def foldMonoidal[A : Monoid](f: Element => A): A =
      Monoid.combine(f(this), Monoid.combineAll(els.map(f)))
...

e1.foldMonoidal(_.value)

One issue with that though is that you lose the information of the nested structure: You may as well have just a list of (name, value).

Any nested data structure can have a fold operation defined for it, in a way that keeps knowledge of its structure. In your case, this would be:

def fold[A](f: (Element, List[A]) => A): A =
  f(this, els.map(_.fold(f)))
...
e1.fold[Int]((el, list) => el.value + list.sum)

You can see this allows more freedom, e.g. you may want to sum the value with the average of the nested elements, which you couldn't do with the monoidal solution above.

e1.fold[Double]((el, list) => el.value + list.sum / list.size)

Or for pretty-printing:

e1.fold[String]((el, strEls) => s"(${el.name} -> ${el.value}, ${strEls.mkString("[", ",", "]")}")
// (Zero -> 0, [(One -> 1, [(Two -> 2, [(Three -> 3, [],(Four -> 4, []]],(Five -> 5, [(Six -> 6, [],(Seven -> 7, [],(Eight -> 8, [(Nine -> 9, [],(Ten -> 10, []]]]
\$\endgroup\$
  • \$\begingroup\$ I know I am not supposed to thank you, but THANK YOU! \$\endgroup\$ – Ahmad Ragab Jan 6 '18 at 3:13
  • 1
    \$\begingroup\$ In case anyone runs into this the implementation of foldMonoidal should be: def foldM[A: Monoid](f: Element => A): A = { Monoid.combine(f(this), Monoid.combineAll(els.map(_.foldM(f)))) } \$\endgroup\$ – Ahmad Ragab Feb 26 '18 at 23:33
  • \$\begingroup\$ True, due to nested structure, missed that +1 \$\endgroup\$ – V-Lamp Feb 27 '18 at 10:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.