## Lens, State Is Your Father

In our last post, we introduced `IOCoalgebra`s as an alternative way of representing coalgebras from an algebraic viewpoint, where `Lens` was used as a guiding example. In fact, lens is an abstraction that belongs to the group of Optics, a great source of fascinating machines. We encourage you to watch this nice introduction to optics because we’ll show more optic examples under the `IOCoalgebra` perspective. While doing so, we’ll find out that this new representation let us identify and clarify some connections between optics and `State`. Finally, those connections will be analyzed in a real-world setting, specifically, in the state module from Monocle. Let us not waste time, there is plenty of work to do!

(*) All the encodings associated to this post have been collected here, where the same sectioning structure is followed.

## Optics as Coalgebras

First of all, let’s recall the `IOCoalgebra` type constructor:

```type IOCoalgebra[IOAlg[_[_]], Step[_, _], S] = IOAlg[Step[S, ?]]
```

As you can see, it receives three type arguments: the object algebra interface, the state-based action or step, and the state type. Once provided, coalgebras are defined as a state-based interpretation of the specified algebra. Take `Lens` as an example of IOCoalgebra:

```trait LensAlg[A, P[_]] {
def get: P[A]
def set(a: A): P[Unit]
}

type IOLens[S, A] = IOCoalgebra[LensAlg[A, ?[_]], State, S]
```

(*) This is a simple Lens, in opposition to a polymorphic one. We will only consider simple optics for the rest of the article.

If we expand `IOLens[S, A]`, we get `LensAlg[A, State[S, ?]]`, which is a perfectly valid representation for lenses as demonstrated by the following isomorphism:

```def lensIso[S, A] = new (Lens[S, A] <=> IOLens[S, A]) {

def from: IOLens[S, A] => Lens[S, A] =
ioln => Lens[S, A](ioln.get.eval)(a => ioln.set(a).exec)

def to: Lens[S, A] => IOLens[S, A] = ln => new IOLens[S, A] {
def get: State[S, A] = State.gets(ln.get)
def set(a: A): State[S, Unit] = State.modify(ln.set(a))
}
}
```

We’ll see more details about lenses in later sections but, for now let’s keep diving through other optics, starting with `Optional`:

```trait OptionalAlg[A, P[_]] {
def getOption: P[Option[A]]
def set(a: A): P[Unit]
}

type IOOptional[S, A] = IOCoalgebra[OptionalAlg[A, ?[_]], State, S]
```

This optic just replaces IOLens’ `get` with `getOption`, stating that it’s not always possible to return the inner value, and thence the resulting `Option[A]`. As far as we are concerned, there aren’t more significant changes, given that `State` is used as step as well. Thereby, we can move on to `Setter`s:

```trait SetterAlg[A, P[_]] {
def modify(f: A => A): P[Unit]
}

type IOSetter[S, A] = IOCoalgebra[SetterAlg[A, ?[_]], State, S]
```

In fact, this is a kind of relaxed lens that has lost the ability to “get” the focus, but is still able to update it. Notice that `set` can be automatically derived in terms of `modify`. Again, `State` is perfectly fine to model the step associated to this optic. Finally, there is `Getter`:

```trait GetterAlg[A, P[_]] {
def get: P[A]
}

type IOGetter[S, A] = IOCoalgebra[GetterAlg[A, ?[_]], Reader, S]
```

This new optic is pretty much like a lens where the `set` method has been taken off, and it only remains `get`. Although we could use `State` to represent the state-based action, we’ll take another path here. Since there isn’t a real state in the background that we need to thread, ie. we can only “get” the inner value, `Reader` could be used as step instead. As an additional observation, realize that `LensAlg` could have been implemented as a combination of `GetterAlg` and `SetterAlg`.

There are still more optics in the wild, such as `Fold` and `Traversal`, but we’re currently working on their corresponding IOCoalgebra representation. However, the ones that have already been shown are good enough to establish some relations between optics and the state monad.

## Optics and State Connections

Dealing with lenses and dealing with state feels like doing very similar things. In both settings there is a state that could be queried and updated. However, if we want to go deeper with this connection, we need to compare apples to apples. So, what’s the algebra for `State`? Indeed, this algebra is very well known, it’s named `MonadState`:

```trait MonadState[F[_], S] extends Monad[F] {
def get: F[S]
def put(s: S): F[Unit]

def gets[A](f: S => A): F[A] =
map(get)(f)

def modify(f: S => S): F[Unit] =
bind(get)(f andThen put)
}
```

This `MonadState` version is a simplification of what we may find in a library such as scalaz or cats. The algebra is parametrized with two types: the state-based action `F` and the state `S` itself. If we look inside the typeclass, we find two abstract methods: `get` to obtain the current state and `put` to overwrite it, given a new one passed as argument. Those abstract methods, in combination with the fact that `MonadState` inherits `Monad`, let us implement `gets` and `modify` as derived methods. This sounds familiar, doesn’t it? It’s just the lens algebra along with the program examples that we used in our last post! Putting it all together:

```trait LensAlg[A, P[_]] {
def get: P[A]
def set(a: A): P[Unit]

def gets[B](
f: A => B)(implicit
F: Functor[P]): P[B] =
get map f

def modify(
f: A => A)(implicit
get >>= (f andThen set)
}
```

(*) Notice that we could have had `LensAlg` extending `Monad` as well, but this decoupling seems nicer to us, since each program requires only the exact level of power to proceed. For instance, `Functor` is powerful enough to implement `gets`, so no `Monad` evidence is needed.

Apparently, the only difference among `LensAlg` and `MonadState` lies in the way we use the additional type parameter. On the one hand, `LensAlg` has a type parameter `A`, which we understand as the focus or inner state contextualized within an outer state. On the other hand, we tend to think of `MonadState`‘s `S` parameter as the unique global state where focus is put. Thereby, types instantiating this typeclass usually make reference to that type parameter, as one could appreciate in the `State` instance for `MonadState`. However, we could avoid that common practice and use a different type as companion. In fact, by applying this idea in the previous instance, we get a new lens representation:

```type MSLens[S, A] = MonadState[State[S, ?], A]
```

(*) The isomorphism between `IOLens` and `MSLens` is almost trivial, given the similarities among their algebras. Indeed, you can check it here.

Lastly, we can’t forget about one of the most essential elements conforming an algebra: its laws. `MonadState` laws are fairly known in the functional programming community. However, the laws associated to our `LensAlg` aren’t clear. Luckily, we don’t have to start this work from scratch, since lens laws are a good starting point. Despite the similarity between both packages of laws (look at their names!) we have still to formalize this connection. Probably, this task will shed even more light on this section.

## Monocle and State

Connections between optics and state have already been identified. Proof of this can be found in Monocle, the most popular Scala optic library nowadays, which includes a state module containing facilities to combine some optics with State. What follows is a simplification (removes polymorphic stuff) of the class that provides conversions from lens actions to state ones:

```class StateLensOps[S, A](lens: Lens[S, A]) {
def toState: State[S, A] = ...
def mod(f: A => A): State[S, A] = ...
def assign(a: A): State[S, A] = ...
...
}
```

For instance, `mod` is a shortcut for applying `lens.modify` over the standing outer state and returning the resulting inner value. The next snippet, extracted from Monocle (type annotations were added for clarity), shows this method in action:

```case class Person(name: String, age: Int)
val _age: Lens[Person, Int] = GenLens[Person](_.age)
val p: Person = Person("John", 30)

test("mod") {
val increment: State[Person, Int] = _age mod (_ + 1)

increment.run(p) shouldEqual ((Person("John", 31), 31))
}
```

That said, how can we harness from our optic representation to analyze this module? Well, first of all, it would be nice to carry out the same exercise from the `IOLens` perspective:

```case class Person(name: String, age: Int)
val _ioage: IOLens[Person, Int] =
IOLens(_.age)(age => _.copy(age = age))
val p: Person = Person("John", 30)

test("mod") {
val increment: State[Person, Int] =
(_ioage modify (_ + 1)) >> (_ioage get)

increment.run(p) shouldEqual ((Person("John", 31), 31))
}
```

Leaving aside the different types returned by `_age mod (_ + 1)` and `_ioage modify (_ + 1)`, we could say that both instructions are pretty much the same. However, `mod` is an action located in an external state module while `modify` is just a primitive belonging to `IOLens`. Is this a mere coincidence? To answer this question, we have formalized this kind of connections in a table:

Monocle State-Lens Action IOLens Action Return Type
`toState` `get` `State[S, A]`
? `set(a: A)` `State[S, Unit]`
? `gets(f: A ⇒ B)` `State[S, B]`
? `modify(f: A ⇒ A)` `State[S, Unit]`
`mod(f: A ⇒ A)` ? `State[S, A]`
`modo(f: A ⇒ A)` ? `State[S, A]`
`assign(a: A)` ? `State[S, A]`
`assigno(a: A)` ? `State[S, A]`

What this table tells us is how the actions correspond to each other. For instance, the first raw shows that toState (from Monocle) corresponds directly with get (from our IOLens), both generating a program whose type is `State[S, A]`. The second raw contains a new element ?, which informs us that there’s no corresponding action for set in Monocle. Given the multitude of gaps in the table, we could determine that we’re dealing with such different stuff, but if you squint your eyes, it’s not hard to appreciate that `mod(o)` and `assign(o)` are very close to `modify` and `set`, respectively. In fact, as we saw while defining `increment`, `mod` is just a combination of `get` and `modify`. So, it seems to exist a strong connection between the `IOLens` primitives and the actions that could be placed in the state module for lenses. The obvious question to be asked now is: Is there such a connection between the state module and other optics? In fact, Monocle also provides facilities to combine `State` and `Optional`s, so we can create the same table for it:

Monocle State-Optional Action IOOptional Action Return Type
`toState` `getOption` `State[S, Option[A]]`
? `set(a: A)` `State[S, Unit]`
? `gets(f: A ⇒ B)` `State[S, Option[B]]`
? `modify(f: A ⇒ A)` `State[S, Unit]`
`modo(f: A ⇒ A)` ? `State[S, Option[A]]`
`assigno(a: A)` ? `State[S, Option[A]]`

Again, the results are very similar to the ones we extracted from `IOLens`. In fact, we claim that any `IOCoalgebra`-based optic which can be interpreted into `State` may contain a representative in the state module, and the actions that the module may include for each of them are just its associated primitives and derived methods. But, what about `Getter`s, where both `State` and `Reader` are suitable instances? Well, the `State` part is clear, we can add a new representative for `Getter` in the state module. However, the interesting insight comes with `Reader`: identifying new interpretations means identifying new modules. In this sense, we could consider including a new module reader in the library. Obviously, we could fulfill that module by following the same ideas that we showed for state.

To sum up, by following this approach, we have obtained a framework to systematically determine:

• The appropriateness of including a new module.
• The optics that it may support.
• The methods it may contain for every optic.

This is a nice help, isn’t it?

## Discussion and Ongoing Work

Today, we have seen that `IOCoalgebra`s served us two purposes, both of them involving understandability. First of all, we have identified an unexpected connection between `Lens` and the `State Monad`. In fact, we have defined `Lens` in terms of `MonadState`, so we had to explain `Lens` who was his biological father, and that was tough for her! Secondly, we have described a systematic process to create and fulfill Monocle’s peripheral modules, such as state. In this sense, if we go one step further, we could think of those peripheral modules as particular interpretations of our optic algebras. This perspective makes the aforementioned process entirely dispensable, since optic instances would replace the module itself. As a result, logic wouldn’t end up being contaminated with new names such as `assign` or `mod`, when all they really mean is `set` and `modify`, respectively.

As we mentioned before, we still have to translate other optics into their corresponding `IOCoalgebra` representation and identify the laws associated to the algebras. Besides, we focused on simple optics, but we should contemplate the polymorphic nature of optics to analyze its implications in the global picture. Anyway, optics are just a source of very low-level machines that conform one of the first steps in the pursue of our general objective, which is programming larger machines, ie. reactive systems, by combining smaller ones. It’s precisely within this context where our optics, in combination with many other machines from here and there, should shine. In this sense, there’s still a lot of work to do, but at least we could see that isolating algebras from state concerns has turned out to be a nice design pattern. 