Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Should my monoid be left- or right-biased?

Tags:

haskell

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?

like image 704
fredefox Avatar asked Sep 17 '18 10:09

fredefox


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

like image 126
chi Avatar answered Oct 13 '22 00:10

chi