Free.foldMap is not stack safe

[ceedubs]

This is a followup to #713. #702 made Free.foldMap stack safe (and added a test for this), but unfortunately it had to be backed out because it introduced a bug. Currently the stack safety test for foldMap is ignored.

There was some discussion in #713 as to what should happen for this. I'm no expert in the matter. I'm hoping some others such as @mandubian or @adelbertc might be able to weigh in.

[TomasMikula]

We can implement a stack-safe foldMap using MonadRec[M]. The question is, do we

1. keep the current foldMap, which is stack-safe only for lazy (trampolined) monads, and add the stack-safe version as foldMapRec; or
2. change the current method, only allowing foldMap with tail-rec monads.

I would be leaning more towards 2., to promote stack-safety by default. For cases where people don't have a stack-safe monad, but stack-safety is not a problem b/c their Free structure is shallow, they can always provide a fake MonadRec[M] instance. Or we could even keep the original method as foldMapUnsafe.

[mandubian]

I suppose it brings also constant-stack execution, right?
By default, stack-safety is clearly preferred because when it bites, it bites hard & randomly.
But, it would be cool to check the cost on perfs with MonadRec.

[TomasMikula]

@mandubian my definition of stack-safety is constant-stack usage, so I don't understand your first question.

Regarding the latter, are there some existing Free benchmarks?

[mandubian]

I don't think there are benches but it would be useful ;)