What is Store in scalaz

I'm trying to understand Lenses in scalaz (surprisingly didn't find something similar in cats-core) and I came across the so called Store which is a type alias:

type StoreT[F[_], A, B] = IndexedStoreT[F, A, A, B]
type IndexedStore[I, A, B] = IndexedStoreT[Id, I, A, B]
type Store[A, B] = StoreT[Id, A, B]

Where

final case class IndexedStoreT[F[_], +I, A, B](run: (F[A => B], I))

The question is how to treat this type? The documentation just referes to Lenses. Can someone give an explanation in a few words?

To me it looks similar to State monad where the "state transition" is storing with function F[A => B]

A Store[S,A] is a structure full of As, indexed by S, with a distinguished S as a kind of "cursor" into the structure.

To answer the question "what is it?", it's most instructive to look at what operations it supports.

You can ask for the position of the cursor:

_.pos : Store[S,A] => S

You can "peek" at the value under the cursor:

_.peek : Store[S,A] => A

And you can "seek" to move the cursor:

_ seek _ : (Store[S,A], S) => Store[S,A]

Think of it as an array of dimensions S, where you have an index s:S into the array, and you can move the index.

For example, Store[(Int,Int), Byte] is a two-dimensional 256-colour bitmap. You can peek at the colour (represented by a byte) of the pixel under the cursor, and you can move the cursor to a different pixel using seek.

The store comonad

Store[S,_] is also a comonad. This means it supports the following operations:

map : (A => B) => (Store[S,A] => Store[S,B])
extend : (Store[S,A] => B) => (Store[S,A] => Store[S,B])
duplicate : Store[S,A] => Store[S, Store[S, A]]

map means you can change all the values in the store using a function.

s.extend(f) takes a "local" computation f, that operates on the store at a particular location of S, and extends it to a "global" computation that operates on the store at every location. In the bitmap example, if you have a function mean(store) that takes the average of the pixels immediately surrounding the cursor in the store, then store.extend(mean) will perform a Gaussian filter on the whole image. Every pixel in the new image will be an average of the pixels immediately surrounding the pixels at that location in the original image.

s.duplicate gives you a Store[S,Store[S,A]] full of Store[S,A]s, that at every location S has a copy of the original Store[S,A] with its cursor set to that location S.

Relation to State

Store is the dual of State. Under the hood, State[S,A] is really S => (A, S), and Store[S,A] is really (S => A, S):

State[S,A] ~= S => (A, S)
Store[S,A] ~= (S => A, S)

Both are composed of the two functors S => _ and (_, S). If you compose them one way, you get State[S,_]. If you compose them the other way, you get Store[S,_].

I gave a talk about this a couple of times:

https://www.youtube.com/watch?v=FuOZjYVb7g0

A cool way you can exploit this duality is that if you have a store and a state machine, they annihilate each other. The store drives the state machine, and in turn the state machine picks a value from the store.

def zap[S,A,B](state: State[S,A], store: Store[S,B]): (A,B) = {
  val (a, s) = state.run(store.pos)
  (a, store.seek(s).peek)
}