Should my monoid be left- or right-biased?

  • A+
Category:Languages

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?

 


(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.

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: