What I love the most.
Let's sort out some overhyped bullshit.
This is an attempt to formalize the general notion of absence, of nothing instead of something, of an empty slot. In the world of enzymes there could be a slot for a protein, which might be empty or filled with a certain protein (actually a certain pattern of a bigger structure).
This notion is related to the mathematical (abstract) notion of zero, denoted by the symbol
0. In math a zero could be obtained by
f(x) = x - x, however in reality if something is not (or no longer) there, it is just no longer there. There is no notion of 0 of every possible particles or other similar abstract nonsense.
Same, BTW, goes to negation. NON-apple makes no more sense than zero apples. However, not apples (except apples) makes sense.
In the languages of DNA transcription there is, obviously, no
0 (Notion of nothingness requires an intelligent observer which is absent). Empty slot in an enzyme is just an empty slot, it is not a state of zero or all that crap. Emptiness is concrete, nothingness is abstract.
data Maybe a = Nothing | Just a
Which must be rather
Empty | Contains a.
This an attempt to formalize the general notion of grouping (combining pieces, say drops of water, together).
The notion of Semigroup is to have an associative binary operation
(<>) such that it confirms to the Associativity Law, which means that order of operations does not matter.
(1 + 3) + 5 = 1 + (3 + 5). Addition for Numbers
(+) is an associative operation. So is concatenation for Lists
[1,3] (++)  =  (++) [3,5].
Cons, however, is not.
the Associativity Law in pseudocode:
x <> (y <> z) = (x <> y) <> z
where a generic associative function
(<>) has the type
(<>) :: a -> a -> a
Which means it produces a new value of the same type, by combining two values
Let's state it in plain English: to be a Semigroup is to have an associative binary operation defined and to have a concatenation (merging into one) function in terms of this associative operation. It could be the same function, like the binary
(+) for Numbers and the binary
(++) for Lists.
Addition is an example of an associative operation (conforms to the Associativity Law)
x + (y + z) = (x + y) + z
+ is a binary combinator. Binary stand for arity of 2. It requires exactly two arguments. No more, no less.
For addition, due to the abstract nature of numbers, the order of arguments of binary operation
(+) does not matter -
1 + 2 = 2 + 1 while for lists
[1, 2] is not the same as
[2, 1], because Lists have a concrete ordered structure which Numbers or Sets lack.
This is the notion that adding Hydrogen to Hydrogen-and-Oxygen is the same as adding Hydrogen-and-Oxygen to another Hydrogen.
Reduction of an aggregate
Reduction is application of a combinator to an aggregate. Some enzymes could be viewed as combinators (reducers), while most of them are mappers (transducers).
Reduce a list of numbers with
(+ 1 2 3 4) 10
reduction applied to nothing is identity (the notion of having no effect)
There is also notion of concatenation (merging together into one) associated with a Semigroup.
In typed lambda calculus it is required to define the notion of
NonEmpty which basically means material, existing, because concatenation of something cannot be nothing and in order not to blow up combinators applied to the elements of an aggregate (as if aggregates of the Nature MUST ALWAYS BE homogeneous!).
Concatenation is an instance of reduction (arithmetic addition could be viewed as concatenation for a
List of numbers).
sconcat :: NonEmpty a -> a sconcat (a :| as) = go a as where go b (c:cs) = b <> go c cs go b  = b
sconcat stands for semi-group concatenation,
(:|) stands for
Monoids are semi-groups with identity (having no effect) and emptiness (nothing).
Monoid Laws in pseudocode
- adding nothing produces no effect, order of operations does not matter
mempty incidentally (unintentionally) beautifully stands for Marked (tagged) Empty, because there is no such thing as nothing in Nature.
x <> mempty = x mempty <> x = x
- semi-group law (Associative Law)
x <> (y <> z) = (x <> y) <> z
- concatenation (merging into one)
mconcat = foldr (<>) mempty
Notice that beside the notion of grouping only abstract notions of
Sum (addition) and
Product (multiplication) corresponds to (form a) Monoid.
Set is a formalized notion of a group of abstract entities, originally defined on Numbers. It implies notion of membership (inclusion) and does not have the notion of ordering and hence duplicate values. (Each instance of a Number is referred to the same Number - there is no duplicates among Numbers).
A set might be empty or contain arbitrary values, including other sets, unrestricted to be homogeneous. The only notion is of membership, which is defined as a set of operations on elements (addition, check-for-membership, removal of an element).
At a higher level of abstraction a Set could be viewed as a
Iterable or even
Traversable, but the order of elements selected is arbitrary. Each element must be selected exactly once.
A List is a possible empty "concrete" ordered sequence, may include arbitrary items, including duplicates.
Only Homogeneous Lists are instances of Monoid (while
NonEmpty homogeneous List is an instance of a Semi-Group).
This is exactly the place where the glimpse of bullshit is caught for the first time - the whole thing is defined only for homogeneous lists, and associativity is defined only for
NonEmpty homogeneous lists (because it has been modelled on numbers, and numbers are not real).
To put it simply - all this hierarchy of abstract crap is just artificially imposed mental construct. All this formalism is applicable only to abstract numbers and other restricted homogenous abstract concepts, not to "concrete" atoms or processes of reality.
Nevertheless this formalism is occasionally useful in typed lambda calculus because it help caught type mismatches in function application.
The whole thing
The basic notions
- Grouping (combining)
append = <>using an associative operation
- Reduction (folding)
using a combinator
- Concatenation (merging)
concat = fold <> 
- Concatenation (merging)
class Semigroup a where (<>) :: a -> a -> a sconcat :: NonEmpty a -> a sconcat (a :| as) = go a as where go b (c:cs) = b <> go c cs go b  = b stimes :: Integral b => b -> a -> a stimes = stimesDefault
class Semigroup a => Monoid a where mempty :: a mappend :: a -> a -> a mappend = (<>) mconcat :: [a] -> a mconcat = foldr mappend mempty
instance Semigroup [a] where (<>) = (++) stimes = stimesList
instance Monoid [a] where mempty =  mconcat xss = [x | xs <- xss, x <- xs]
instance Semigroup (NonEmpty a) where (a :| as) <> ~(b :| bs) = a :| (as ++ b : bs)
instance Semigroup b => Semigroup (a -> b) where f <> g = \x -> f x <> g x stimes n f e = stimes n (f e)
Maybe forms a Semigroup, why not?
instance Semigroup a => Semigroup (Maybe a) where Nothing <> b = b a <> Nothing = a Just a <> Just b = Just (a <> b) stimes = stimesMaybe
Folding is a generalized reduction [of a structure to a single value], given a binary combinator and initial value (mempty or identity)
Folding implies a structure. A
To traverse a structure means to visit (to select) each element of it exactly once.
A single value can be traversed, a linear structure, a tree, an acyclic graph is traversable, general graph (a network) is not traversable. An empty structure is traversable.
Traversable, and a folds are just a family of high order functions.
The accompanying metaphor is the process of folding of something spread into something folded.
class Foldable (t :: * -> *) where ... foldr :: (a -> b -> b) -> b -> t a -> b ...
Functor is a formalization of the notion of mapping over everything which could be mapped over. List is an obvious example.
Mapping is a generalized notion of uniformly transforming each element of a structure (in the same way) given a function on elements. The structure is kept intact and completely encapsulated from the function on elements.
The metaphor is that a function does not know that it is used on aggregates.
class Functor (f :: * -> *) where fmap :: (a -> b) -> f a -> f b ...
specialized (implemented) for Lists
map :: (a -> b) -> [a] -> [b]
What is the point of classifying the classic
map as a Functor? None. Except when you are an academic and getting paid for discussing higher pure abstractions.
(define map (lambda (f xs) (foldr (lambda (x xs) (cons (f x) xs)) '() xs)))
which means that we could
map over everything which is
class Functor f => Applicative (f :: * -> *) where ... (<*>) :: f (a -> b) -> f a -> f b ...