Reduce function on custom data structure using Cats Semigroup

Question

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?

• janos: Hi, you flagged your own question to migrate to Stack Overflow. I think it's better here.

Answer 1

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, []]]]

• Ahmad Ragab: I know I am not supposed to thank you, but THANK YOU!
• Ahmad Ragab: 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)))) }
• V-Lamp: True, due to nested structure, missed that +1