Since my last post I have been climbing what I recently heard Julie Moronuki call the Haskell Pyramid. I have been learning about the bread and butter abstractions which Haskell programmers use all the time and serve as useful tools to describe and compose programs. These are not only required knowledge to be able to use most of the really cool Haskell features that excite me (which I will cover in a later post) but also useful ways to model computation in general, even if one is not using Haskell.

I have been learning about SemiGroups, Monoids, Functors, Applicatives, Monads, Foldables, Traversables and Reader from the Haskell Book, which Julie co-authored. I figured that now would be a good time to take stock of what I have learned. This is meant to be a fly by of these topics, more of a cheatsheet than a tour. If you want to learn more about these topics, I recommend checking out Haskell Book. All the exercises I worked through to gain an intuition about these abstractions can be found here

SemiGroup, Monoid, Functor, Applicative, and Monad are abstractions, which have laws, which concrete implementations must conform to in order to be a valid instances of that abstraction. While learning about these abstractions, I used QuickCheck, a property based testing library, to verify that the instances I wrote conformed to the appropriate laws. I found this to be an extremely effective way to learn new concepts because my test suite was able to serve as a constant feedback loop.

#### SemiGroup

As described on the Hackage SemiGroup package, a SemiGroup is an algebraic structure, consisting of a set together with an associative, binary operation (`<>`

).
the
I know this function `<>`

is called `mappend`

if on Monoid, but I don't know
what it is called on SemiGroup.

In order for something to be a valid SemiGroup it's `<>`

function must be binary
(take two arguments) and associative:

```
a <> (b <> c) == (a <> b) <> c
```

Some things that exhibit SemiGroup behavior include non empty lists, and getting
the first and last elements from a sequence of (`<>`

) calls:

First 1 <> First 2 <> First 3 => First 1

Last 1 <> Last 2 <> Last 3 => Last 3

#### Monoid

Monoids are a SemiGroup that has an identity value (described by `mempty`

) such that:

```
mempty <> x == x
x <> mempty == x
```

All Monoids also have the binary associative function `<>`

which can be inherited
from their SemiGroup instance, and is called `mappend`

(i.e. `<> == mappend`

if it is
being applied to a Monoid).

Numbers (both over multiplication and addition) boolean conjunction (`and`

)
disjunction (`or`

), (`a && b && c`

) and (`a || b || c`

) patterns, list concatenation
and zipping all exhibit Monoidal behavior (i.e. they have an identity value and
a binary associative operation).

Lucy Zhang also showed me that Groups (which I came across when researching Kademlia, the DHT protocol used in BitTorrent and IPFS) are Monoids that have an inverse for every value. An example of groups would be integers over addition, where zero is it's own inverse, and negative numbers and positive numbers are inverses of each other.

Monoids have kind `*`

.

#### Functor

Functors have some structure that is not able to be altered, but which can allow for transformations on values that are not part of the structure. List, Maybe, Either, Tuples, and functions are all functors.

They implement `fmap`

, which can also be written as `<$>`

.

fmap :: Functor f => (a -> b) -> f a -> f b

and have the following laws which they must obey to preserve their structure:

##### identity

```
fmap id == id
```

##### composition

```
fmap (f . g) == fmap f . fmap g
```

If you try to change the structure of a functor it will violate the composition
law, as applying `fmap`

multiple times will yield a different result, than just
applying it once and composing two functions.

Functors must have kind `* -> *`

as they must have a type inhabitant which is not
part of the structure, such as the `Right`

values in the case of `Either`

, or
list elements in the case of Lists .

Lists, functions, and `IO`

are all examples of functors. Function composition, `.`

, is `fmap`

on functions:

(.) :: (b -> c) -> (a -> b) -> (a -> c)

where `f`

is `(-> a)`

.

Something I found profoundly beautiful is when one applies `fmap`

to itself (as
in the example below)

(fmap . fmap) show [Just 1, Just 3, Nothing] => [Just "1", Just "3", Nothing]

the way the types work out requires algebraic substitution of the types:

(.) :: (b -> c) -> (a -> b) -> (a -> c) fmap1 :: Functor f => (a -> b) -> f a -> f b fmap2 :: Functor g => (c -> d) -> g c -> g d

In `fmap . fmap`

the type signature expands out to

```
((a -> b) -> (f a -> f b)) -> ((c -> d) -> (g c -> g d))
```

Because we know that the `b`

in compose

```
(b -> c) -> (a -> b) -> (a -> c)
```

is the same as:

```
(a -> b)
```

in the first fmap, and

```
(g c -> g d)
```

in the second fmap

we know that `f a`

from the first fmap can be rewritten as `f (g c)`

and
`f b`

from the second can be rewritten as `f (g d)`

,

which means we can rewrite our type signature for `fmap . fmap`

as

```
(c -> d) -> (f (g c) -> f (g d))
```

which describes at the type level transforming a value within a functor, within a functor.

It absolutely blew my mind that you could work that out from the types alone without needing to think about what is happening at the value level at all.

On `Maybe`

or `Either`

, `Nothing`

and `Left`

values are ignored by `fmap`

because they are
part of the structure, which must be left intact in order to comply with the functor
laws.

Functor (unlike Monoid) only has a single valid instance for a given type.

Functors are very useful for transforming values inside of `IO`

. I used
this repeatedly in my QuickCheck testing to transform lists generated by QuickCheck
into other data-structures which I needed for testing.

#### Applicative

As described in the Haskell Book:

"Applicatives are monoidal functors:

- Monoids give us a way to mash data-structures together.
- Functors give us a way do do function application in a structure.
- Applicatives give us away to apply functions which are themselves in a structure over another structure and then mash the structures together."

Applicatives have 2 operations:

pure :: Applicative f => a -> f a

which takes a value of any type and puts it into an applicative context

(<*>) :: Applicative f => f (a -> b) -> f a -> f b

which applies a function in an applicative structure to values in an applicative structure, and combines the two applicative structures.

They must together follow the following laws:

##### Identity

```
pure id <*> v = v
```

##### Composition

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

##### Homomorphism

```
pure f <*> pure x = pure (f x)
```

##### Interchange

```
u <*> pure y = pure ($ y) <*> u
```

If we compare, `$`

(which is just function application), `<$>`

(`fmap`

) and `<*>`

```
$ ::(a -> b) -> a -> b
<$> ::(a -> b) -> f a -> f b
<*> ::(a -> b) -> f a -> f b
```

we see that `fmap`

is jut function application over a functor, and applicative
application is just functorial application, where the function is within a
structure, which implies that the structures must be combined in some way.

`<*>`

lets us do function application on functions in a structure like so:

Just (*2) <*> Just 3 => Just 6

Nothing <*> Just 3 => Nothing

Wrapping a function in `pure`

and applying `<*>`

is the same as just fmapping using
the function.

```
pure f <*> y == f <$> y
```

Applicatives have their structure combined using a monoidal pattern, however because there are multiple possible monoidal patterns on many types, there is no guarantee the applicative will use any specific Monoid instance for that type. Also, there is no typeclass constraint on Applicatives that they must be Monoids.

The function application component will be the same as `fmap`

though, as there
is only one valid functorial instance for a given type.

#### Monad

As Nick Collins explained during our
Haskell Study group, Monad's bind (`>>=`

) is nothing more than flatMap.

Definition:

class Applicative m => Monad m where (>>=) :: m a -> (a -> m b) -> m b (>>) :: m a -> m b -> m b return :: a -> m a

I also learned about the fish operator:

(>=>) Monad m -> (a -> m b) -> (b -> m c) -> a -> m c

I don't have much to say about monads other than if you just treat them like things which support flatMap (whereby you are able to flatten out structures generated from calling bind, while adding new resulting values to the new structure) I find that they become a lot easier to work with and reason about.

#### Foldable:

Foldable (which is a typeclass which allows your
data-structure to be folded over), requires only either
`foldr`

or or `foldMap`

to be defined. If you define `foldMap`

you need for the type to also have a Monoid instance so you are able to use
`mappend`

/ `mconcat`

to summarize the Monoid structures you are folding over.

By defining a foldable instance for your type, you are also able to get a number of convenience functions which can be written using folding functions inferred automatically including:

foldl' :: (b -> a -> b) -> b -> t a -> b toList :: t a -> [a] null :: t a -> Bool length :: t a -> Int elem :: Eq a => a -> t a -> Bool maximum :: forall a. Ord a => t a -> a minimum :: forall a. Ord a => t a -> a sum :: Num a => t a -> a product :: Num a => t a -> a

While learning about Foldable with Santiago Gepigon
during the Haskell Study Group, we also learned about the `ScopedTypeVariables`

language extension and how it is needed to define type signatures for
polymorphic functions defined in where clauses.

#### Traversable:

As described in the book:

"Traversable allows you to transform elements in a structure (like functor) while producing applicative effects along the way, and lift the (potentially multiple) applicative effects outside of the traversable structure."

Has 2 functions:

sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)

traverse :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)

Here are some examples of how they work:

sequenceA [Just 1, Just 2, Just 3] => Just [1,2,3] sequenceA [Just 1, Just 2, Nothing] => Nothing sequenceA :: (Traversable t, Applicative f) => -> t (f a) -> f (t a) traverse :: (Traversable t, Applicative f) => (a -> f a) -> t a -> f (t a)

`traverse`

must follow the following laws:

##### Naturality

```
t . traverse f = traverse (t . f)
```

##### Identity

traverse Identity = Identity

##### Composition

traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

`sequenceA`

must follow the following laws:

##### Naturality

```
t . sequenceA = sequenceA . fmap t
```

##### Identity

sequenceA . fmap Identity = Identity

##### Composition

sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

Traverse is really useful when you have a traversable and you need to transform
it into an applicative of a traversable, while converting each element to an
applicative and applying `<*>`

to the intermediate values.

#### Reader

As mentioned above, functions (`(->) r`

) are functors and `(.) == fmap`

. The `r`

is part of the functoral
structure, and therefor the only thing that can change with `fmap`

application is
the return value of the function.

(`Reader r a`

) is just a wrapper around function composition.

The `r`

from `Reader`

here is part of the `f`

structure, so it gets applied with the first argument:

pure :: a -> f a pure :: a -> (r -> a) (<*>) :: f (a -> b) -> f a -> f b (<*>) :: (r -> a -> b) -> (r -> a) -> (r -> b)