Should my monoid be left- or right-biased?

user_1021134 0
Viewed 209

The monoid instance for [a] is left-biased. One way to demonstrate what I'm aiming at is with the following two definitions:

good ∷ Applicative f ⇒ Semigroup (f ()) ⇒ f ()
good = pure () <> good

bad ∷ Applicative f ⇒ Semigroup (f ()) ⇒ f ()
bad = bad <> pure ()

Here we can see that good @[] is productive whereas bad @[] diverges. The same issue can have similar consequences for performance (runtime and memory usage). So my question is, is there a general guideline for whether I should design my semigroup to be left- or right biased? I'd argue that similar things should be taken into consideration when writing/using Foldables. Perhaps this is the reason that both foldl and foldr are instance methods?

haskell
2 Answers

(This is a bit opinion based, but I will answer anyway)

Other things being equal, I would make it left-biased.

I'm suggesting that only because there already are left-biased monoids ([a]), and I can't think of any existing right-biased ones. (Well, snoc-lists, but these are far less common.)

Further, left-to-right is a common order for "effects" like non-termination, or applicatives/monads. I would argue that most programmers are already used to such order of effect-sequencing.

user_32349590

Left-biased makes sense because that's the way the <> operator associates naturally, without parentheses:

good = pure () <> pure () <> pure () <> ...
bad = ((... <> pure ()) <> pure()) <> pure ()

This is a bit of a chicken & egg of course, because this associativity was chosen so lists would perform properly. But there we are.

user_7459030
Related