Optics -- a composable way to express data access and manipulation which works great in tandem with immutability -- are becoming more popular (something which the author tries to push even further.) Whereas we have a good story about the relation between optics, and their practical usage, their implementation seems always quite complex: van Laarhoven lenses and profunctor optics usually rank high as the way to encode these ideas. In this blog post my goal is to show another encoding, which has the advantage of reusing one of our best friends: monads.
Let's forget for a moment the "setting" behavior you find in some lenses, and focus on the "getting" part. Setting is of course important, but has no interesting hierarchy associated with it; those optics simply provide a function:
over :: Setter s a -> (a -> a) -> s -> swhich lifts a modification in the inner component to a modification in the bigger object.
The "getting" part, on the other hand, requires a hierarchy, because data may not always be there, or may consist of more than one part. Using the names from Haskell's optics package, these correspond to the following optics and operations:
view :: Getter s a -> s -> a
preview :: AffineFold s a -> s -> Maybe a
toListOf :: Fold s a -> a -> [a]Instead of using a more complex encoding, we could say that Getter, AffineFold, and Fold are their basic operation. For example:
type AffineFold s a = s -> Maybe aOne of the main features of optics, as discussed above, is their composability. In particular, we want to define a (%) operation (again, following the optics convention) which "digs into" two levels of data. Let's begin by composing only optics of the same kind:
(%) :: AffineFold a b -> AffineFold b c -> AffineFold a c
-- (%) :: (a -> Maybe b) -> (b -> Maybe c) -> (a -> Maybe c)You can surely write the definition on your own. But the observation is that this operation is nothing else that composition for Kleisli arrows, that is, functions of the form a -> m b for a monad m. In Haskell, this is also known as the "fish operator":
(%) = (>=>)This points us towards a way to unify the different getters. Let's look once again at the three operations, but with a small twist on the single-valued one: we are going to wrap the return value in the "do-nothing monad" Identity.
view :: Getter s a -> (s -> Identity a )
preview :: AffineFold s a -> (s -> Maybe a )
toListOf :: Fold s a -> (a -> [a])Now we can clearly see that all three return nothing else than Kleisli arrows for different monads. We can thus unify all three under a single concept:
newtype Getter m s a = Getter { get :: s -> m a }Another advantage is that Kleisli arrows come with a lot of interesting behavior on their own. For example, we can give Applicative and Alternative instances, which provide similar functionality as their monoidal structure in other packages:
instance Applicative m => Applicative (Getter m s)
instance Alternative m => Alternative (Getter m s)Our current composition operator (%) is not the one we want, since it cannot operate on optics of different kind. In order to tackle that problem, let's first look at a related one: how to treat an optic in a "more lenient" way. For example, one should be able to use an AffineFold as a Fold, because "having 0 or 1 elements" is more strict than "having any amount of elements". This is something we can do:
affineFoldToFold :: AffineFold s a -> Fold s a
-- affineFoldToFold :: "s -> Maybe a" -> "s -> [a]"
affineFoldToFold (Getter af) = Getter (maybeToList . af)
where
maybeToList :: Maybe a -> [a]
maybeToList Nothing = []
maybeToList (Just x) = [x]Looking in detail, the main requirement has been the existence of that function maybeToList which goes from Maybe to lists regardless of their element type. Category theorists have a name for this: it's a natural transformation from Maybe to list!
Armed with this idea, we can generalize our view function to give you a picture of the getter in any monad you want, provide that this transformation exists. This is a great use for a type class:
class Nat f g where
nat :: f a -> g a
view :: Nat f g => Getter f s a -> s -> g a
view o = nat . get o
cast :: Nat f g => Getter f s a -> Getter g s a
cast o = Getter (view o)Now let's go for the big prize: optics composition. Alone with this natural transformations we can define "one-sided" compositions, in which we know which side of the optics has to be "downgraded" to be less strict one. The key idea is to transform the more strict one before composing:
(<%) :: (Monad g, Nat f g)
=> Getter g a b -> Getter f b c -> Getter g a c
o <% p = Getter $ get o >=> get (cast p)This is quite annoying, nobody want to keep track of these implementation details, just compose optics and let the compiler figure that out. Let's pull the final trick, inspired by the Join type family in optics. Everything we need to know to compose two getter is what is the "less strict" one of the two, and we can do so via a type family:
type family Join (f :: * -> *) (g :: * -> *) :: * -> *
-- identity is the most strict one
type instance Join f Identity = f
type instance Join Identity f = f
-- every getter composes with itself
type instance Join [] [] = []
type instance Join Maybe Maybe = Maybe
-- affine folds are more strict than folds
type instance Join Maybe [] = []
type instance Join [] Maybe = []And we finally arrived! We just ensure that the combined monad is the result of Joining the arguments, and we apply the natural transformation in each side:
(%) :: (Nat f (Join f g), Nat g (Join f g), Monad (Join f g))
=> Getter f a b -> Getter g b c -> Getter (Join f g) a c
o % p = Getter $ get (cast o) >=> get (cast p)You can generalize this construction for optics with "setting" behavior. There is nothing particularly interesting, since set components compose directly.
data Optic m s a
= Optic { get :: s -> m a, set :: (a -> a) -> s -> s }A bit more interesting is catering for both cases. The most direct translation goes through GADTs, which allow us to distinguish whether the optic has a setter or not.
data HasSet = SetNay | SetYeah
data Optic m h s a where
Getter :: (s -> m a) -> Optic m 'SetNay s a
Optic :: (s -> m a) -> ((a -> a) -> s -> s) -> Optic m 'SetYeah s aAs we did for joining the return monads, we need a SetJoin operator which says how combination of the "having setter" property works. Since we now have a closed set of values, we can use a closed type family instead:
type family SetJoin x y where
SetJoin 'SetNay _ = 'SetNay
SetJoin _ 'SetNay = 'SetNay
SetJoin _ _ = 'SetYeahThe composition operator now gets a longer type, but it's implementation is merely pattern matching on Getter or Optic and combine its components as we have done before.
(%) :: (Nat f (Join f g), Nat g (Join f g), Monad (Join f g))
=> Optic f x a b -> Optic g y b c
-> Optic (Join f g) (SetJoin x y) a cThe fact that we can see getters as Kleisli arrows opens up a lot of connections between optics and monads. Furthermore, we can investigate new optics by changing the monad: what about using Set or Map k?