,
11 tweets,
3 min read
Read on Twitter
Welcome to the second episode of #monadicmonday! Today we'll talk about algebraic data types, and more specifically – about semirings and rings.
First of all, let's recap what a semiring is.
Semiring is a set equipped with two binary operations, called "addition" and "multiplication". The intuition that works here is such of natural numbers – you can define a semiring for Nat with addition as "+" and multiplication as "*"
Semiring is a set equipped with two binary operations, called "addition" and "multiplication". The intuition that works here is such of natural numbers – you can define a semiring for Nat with addition as "+" and multiplication as "*"
A ring extends a semiring with an additional "inverse" operation (or, strictly speaking, ring implies that for each 'a' there exists '-a').
Rings and semirings must also have "zero" and "one" elements, and multiplication should distribute over addition.
Rings and semirings must also have "zero" and "one" elements, and multiplication should distribute over addition.
The other important characteristic is that rings and semirings form a monoid under multiplication.
Recap: monoid is defined using two operations:
- combine :: A×A → A, which merges two monoids together,
- empty :: A, which defines an entity for "one".
Recap: monoid is defined using two operations:
- combine :: A×A → A, which merges two monoids together,
- empty :: A, which defines an entity for "one".
Let's define a ring instance for Option (Maybe) data type. We can define it in several possible ways, and it depends on how we treat "None" value. I've called those instances "safe ring" and "strict ring". 
Given a few different Option instances, we can observe different behavior of our rings:
Strict rings:
Or we can mix&match a bit:
If you can identify a structure as a (semi)ring, you can use its properties with confidence. For example:
- set of languages form a semiring with product as string concatenation and addition as set union;
- boolean logic naturally forms a semiring: (Boolean, &&, ||, true, false).
- set of languages form a semiring with product as string concatenation and addition as set union;
- boolean logic naturally forms a semiring: (Boolean, &&, ||, true, false).
Fun fact: semiring is sometimes called "rig", because a riNg without Negative is just a "rig" ¯\_(ツ)_/¯
I would like to give credit to @LukaJacobowitz for his awesome article "A Tale on Semirings", which I recommend for reading:
lukajcb.github.io/blog/functiona…
lukajcb.github.io/blog/functiona…
