Only 5 real types
I’m about to reveal a secret! Well, it’s not quite a secret, but it’s probably not very obvious if you just superficially looked at documentation and codabase, but here you go…
There are only 5 real types in Я: Void, Unit, Sum, Product and Arrow. That’s it! The rest is on newtype wrappers.
In this chapter I’m going to describe how to use them, how to wrap/unwrap them and why they are important.
Choosing between parameters
On of the most important feautures of Я is that you can map any parameters of all types (except labels). Mapping single slot (arity is 1) functors is easy:
Only 0: Only Integer
Only 0 `yo` (+ 99) ===> Only 100Let’s say we have a product type, structurally it contains two elements - and type declaration reflects this fact:
x = 12345 `lu` True Unit: Integer `P` BooleanType declaration above is written in infix form, here is its prefix form:
(Integer `P` Boolean) ~ ((P) Integer Boolean)How would we choose over which argument we should map? In vanilla Haskell they just take rightmost argument and use a wrapper in case - at least for functions:
instance Functor ((->) e) where
fmap f g = f . g
newtype Op a b = Op { getOp :: b -> a }
instance Contravariant (Op a) where
contramap f g = Op (getOp g . f)In contrast to that mess, Я treats parametricity issues very serious! If there is more than one parameter in a functor, we have to use a special wrapper:
newtype T'I'II u i ii = T'I'II (u i ii)
newtype T'II'I u i ii = T'II'I (u ii i)These two newtype declarations look a like, but the second one flips parameters - this is the trick to put a first parameter to a rightmost position so that we can map over it:
x = (12345 `lu` True Unit): P Integer Boolean
T'I'II `hv` x: T'I'II P Integer Boolean
T'II'I `hv` x: T'II'I P Boolean Integer
(T'I'II x `yo`): (Boolean `AR` o) `AR__` T'I'II P Integer o
(T'II'I x `yo`): (Integer `AR` o) `AR__` T'II'I P Boolean o
(T'I'II x `yo` rewrap not): T'I'II P Integer Boolean
(T'I'II x `yo` rewrap not) ===> T'I'II (12345 `lu` False Unit)
(T'II'I x `yo` (+ 1487)): T'II'I P Boolean Integer
(T'II'I x `yo` (+ 1487)) ===> T'I'II (13832 `lu` False Unit)But as you can see, using exact wrappers is pretty uncomfortable - it’s hard to read such a code. In user code you don’t even have to know their names, you can just use special operators for that (yoi, yio) so visually you can quickly get which parameter you are mapping over:
x = (12345 `lu` True Unit): Integer `P` Boolean
x `yoi` (+ 1487) ===> 13832 `lu` True Unit
x `yio` rewrap not ===> 12345 `lu` False UnitSame thing you can do with sums:
x = (This 12345): Integer `S` Boolean
x `yoi` (+ 1487) ===> This 13832
x `yio` rewrap not ===> This 12345… and with arrows as well, but first parameter is contravariant (yai):
x = (not `ha` odd): Integer `AR` Boolean
x `yai` (+ 1487): Integer `AR` Boolean
x `yio` rewrap not: Integer `AR` BooleanOr, alternatively you can use Hom Functor operators (ha, ho):
x = (False `hu` 0 `la` True `hu` 1): Boolean `AR` Integer
odd: Integer `AR` Boolean
x `ha` odd: Integer `AR` Integer
x `ho` odd: Boolean `AR` Boolean
x `ho` (+1): Boolean `AR` IntegerStateful computations
Essentially stateful computation is just an Arrow that returns tuple, where you put some state alongside result of computation itself (pop):
pop: List item `AR__` Maybe item `P` List itemWe could choose to either return a popped item or modified List - but why would we do it if we can just return a tuple and take whatever we want depends on our needs (at)?
pop `hv` [1,2,3,4,5] ===> Some 1 `lu` [2,3,4,5]
at @(Maybe Integer) `ho` this `ha` pop `hv` [1,2,3,4,5] ===> Some 1
at @(List Integer) `ho` this `ha` pop `hv` [1,2,3,4,5] ===> [2,3,4,5]However composing these computations is not very convenient - we can use that to access state and this to access results:
push: item `AR__` List item `AR_` item `P` List item
that `ha` push `hv` 1 `ha` that `ha` pop `hv` [1,2,3,4,5] ===> [1,2,3,4,5]All stateful-like expressions are defined in this triplet:
xxx: old state `AR__` consequence `P` new state
pop: List item `AR__` Maybe item `P` List itemWe can easily map any parameter in this triplet due extreme composability:
(xxx `yai`) :: (a `AR` old state)
(xxx `yio`) :: (consequence `P` new state `AR` o)
(xxx `yio'yoi`) :: (consequence `AR` o)
(xxx `yio'yio`) :: (new state `AR` o)But these examples are pretty extreme though. Most of the time old state and new state are represented by the same type therefore it could be wrapped in an Event:
(Event `hv` pop): Event (List item) (Maybe item)Mapping become a bit more easier:
(Event `hv` pop `yio`): (Maybe item `AR` o) `AR_` Event (List item) oHowever, we cannot use a regular Arrow here for a first parameter since it’s invariant (appear both in covariant and contravariant positions). But you can use another type of morphisms - Attribute:
(Event `hv` pop `yai`): (a `AT` List item) `AR_` Event a (Maybe item)In vanilla Haskell this behaviour is called zooming - but I avoid names like this at all cost since you should think only about mappings.
To interpret this stateful computation we need to unwrap Event wrapper:
Event `hv` pop `he'hv` [1,2,3,4,5] ===> Some 1 `lu` [2,3,4,5]Take a look at that composition of he and hv operators - it unwraps left expression and apply it (since we get a regular Arrow as a result) to an initial state ([1,2,3,4,5]).
But still, using only Event wrapper we cannot compose stateful expression state-wise. We need another wrapper - State:
x = State `ha` Event `ha` push `hv` 1 `yuk` New `ha` State `ha` Event `hv` popBasically what we are doing on the code snippet above is to push an item atop a List and pop it back so state should not change. In contrast with a previous example, we have 2 asterisk marks there since we need to unwrap both State and Event wrappers:
x `he'he'hv` [2,3,4,5] ===> Some 1 `lu` [2,3,4,5]As it was demonstrated, you can wrap/unwrap expressions in order to use them in different situations. You can consider wrappers as Subtypes and their inner expressions as Supertypes:
Functor compositions
Long story short, we compose functors by treating one of them as an argument of another one:
Maybe (Nonempty List Integer)To get an acccess to Integer, I need to map covariantly twice:
Some [1,2,3,4,5] `yo'yo` (+ 4) ===> Some [5,6,7,8,9]We can use a special wrapper that is used heavily in internal modules in Я to compose functors:
newtype T'TT'I t tt i = T'TT'I (t (tt i))So that if we wrap our Maybe (Nonempty List Integer) into this operator we need to map only once:
T'TT'I `hv` Some [1,2,3,4,5] `yo` (+ 4) ===> Some [5,6,7,8,9]You can use this wrapper’s type as a type operator (just surround it with backticks):
(Optional `T'TT'I` Nonempty List) ~ (T'TT'I Optional (Nonempty List))This wrapper is heavily used in Я internals - soon you are going to realize why.
Common datastructures
In vanilla Haskell List is defined like this:
data List a = [] | a : List aBut in Я it’s defined like this:
type List = Optional `T'TT'I` Nonempty ListSo yes, it’s a composition of Optional and Nonempty List functors!
Optional is a wrapped Sum with a Unit:
type Optional = T'I'II (S) UnitNonempty List is a bit complicated - it’s based on a special newtype:
newtype Recursive f = Recursive (f (Recursive f))This technique is widely known as fixed-point.
To come to an essential Construction there are two more wrappers involded - I will not describe them in details here though:
type Construction = ...
Construction Only ~ Stream
Construction List ~ Tree
Construction Maybe ~ Nonempty ListSome of you can recognize Cofree datatype from vanilla Haskell.
Variety of wrappers
There is actually a variety of wrappers! I didn’t tell about all of them, otherwise this chapter would become too long. The good thing is that on debugging (using GHC) you would always see raw wrappers in a compiler’s output - so you always see internals. It’s not always a good thing though since this output could be huge. But as far as I know you cannot force a compiler to show you type aliases instead - well, I actually didn’t dig into this yet - probably there is a workaround.