Folding on Type without Monoid Instance

Question

I'm working on this Functional Programming in Scala exercise:

// But what if our list has an element type that doesn't have a Monoid instance?
// Well, we can always map over the list to turn it into a type that does.

As I understand this exercise, it means that, if we have a Monoid of type B, but our input List is of type A, then we need to convert the List[A] to List[B], and then call foldLeft.

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B = {
    val bs = as.map(f)
    bs.foldLeft(m.zero)((s, i) => m.op(s, i))
}

Does this understanding and code look right?

Answer 1

First I'd simplify the syntax of the body a bit:

def foldMap[A, B](as: List[A], m: Monoid[B])(f: A => B): B =
  as.map(f).foldLeft(m.zero)(m.ops)

Then I'd move the monoid instance into its own implicit parameter list:

def foldMap[A, B](as: List[A])(f: A => B)(implicit m: Monoid[B]): B =
  as.map(f).foldLeft(m.zero)(m.ops)

See the original "Type Classes as Objects and Implicits" paper for more detail about how Scala implements type classes using implicit parameter resolution, or this answer by Rex Kerr that I've also linked above.

Next I'd switch the order of the other two parameter lists:

def foldMap[A, B](f: A => B)(as: List[A])(implicit m: Monoid[B]): B =
  as.map(f).foldLeft(m.zero)(m.ops)

In general you want to place the parameter lists containing parameters that change the least often first, in order to make partial application more useful. In this case there may only be one possible useful value of A => B for any A and B, but there are lots of values of List[A].

For example, switching the order allows us to write the following (which assumes a monoid instance for Bar):

val fooSum: List[Foo] => Bar = foldMap(fooToBar)

Finally, as a performance optimization (mentioned by stew above), you could avoid creating an intermediate list by moving the application of f into the fold:

def foldMap[A, B](f: A => B)(as: List[A])(implicit m: Monoid[B]): B =
  as.foldLeft(m.zero) {
    case (acc, a) => m.op(acc, f(a))
  }

This is equivalent and more efficient, but to my eye much less clear, so I'd suggest treating it like any optimization—if you need it, use it, but think twice about whether the gains are really worth the loss of clarity.