How to fold a collection of endomorphism with cats

Question

Given a function

def f(i: I) : S => S

I would like to write a pretty common combinator g

def g(is : Seq[I], init: S) : S

The easy implementation uses only classic scala

def g(is : Seq[I], init: S) : S = 
  is.foldLeft(init){ case (acc, i) => f(i)(acc) }

I tried to use Foldable but I encountered a compilation issue.

import cats._
import cats.Monoid
import cats.implicits._
def g(is : Seq[I], init: S) : S = 
  Foldable[List].foldMap(is.toList)(f _)(init)

The error is

could not find implicit value for parameter B: cats.Monoid[S => S] 

I succeeded with State

import cats.data.State
import cats.instances.all._
import cats.syntax.traverse._

def g(is : Seq[I], init: S) : S = 
  is.toList.map(i => State.modify(f(i))).sequenceU.runS(init).value

I have some questions :

1. Is there a Monoid for endomorphism in cats
2. Can you explain compilation issue when I use all import statements together ? Is there a trick to find the right import easily ?
3. Is State a too powerful abstraction in this case ?
4. Is there a better way ?

[update] I've found a workaround for 1.

type Endo[S] = S => S
def g(is : Seq[I], init: S) : S 
  = Foldable[List].foldK[Endo, S](dirs.toList.map(f _))

But I still a foldMapK to avoid boilerplate …

Answer 1

foldMap won't work here because your f is I => S => S, which doesn't match the signature of foldMap:

def foldMap[A, B](fa: F[A])(f: (A) ⇒ B)(implicit B: Monoid[B]): B

you'll need your A => B and B => B => B (the Monoid) separate. f already merged these two operations. Just use foldLeft.