Diagonal setters

[masaeedu]

Sometimes you have a functor from a product category:

class Bifunctor t
  where
  mapBoth :: (a -> a') -> (b -> b') -> t a b -> t a' b'

You can equivalently represent such a functor by a pair of mapping operations:

  mapFirst :: (a -> b) -> t a x -> t b x
  mapSecond :: (a -> b) -> t x a -> t x b
  
  mapBoth f g = mapFirst f . mapSecond g
  
  mapFirst = flip mapBoth id
  mapSecond = mapBoth id

The basic idea behind Setter is to generalize the type (if not the mathematical concept) of fmap. So whereas:

fmap :: forall a b. (a -> b) -> f a -> f b

we have:

type Setter s t a b = (a -> b) -> s -> t

This gives:

• fmap :: forall a b. Setter (f a) (f b) a b

And similarly:

• mapFirst :: forall a b x. Setter (t a x) (t b x) a b
• mapSecond :: forall a b x. (t x a) (t x b) a b

So far so good. Now, sometimes, it is useful to view a Bifunctor as a simple Functor, and use the same morphism to map both type parameters. This can be viewed as precomposing a "diagonal functor" with our Bifunctor:

newtype Diagonal :: (* -> * -> *) -> (* -> *)
newtype Diagonal t a = Diagonal { getDiagonal :: t a a }

instance Bifunctor t => Functor (Diagonal t)
  where
  fmap f = Diagonal . mapFirst f . mapSecond f . getDiagonal

Since we're working with the lens library, we want to forget all about classes and newtypes and work with first class values. So pretending that mapFirst and mapSecond are some arbitrary setters, the basic operation that is being done to them to obtain fmap @Diagonal t above is:

diagonal mapFirst mapSecond = \f -> mapFirst f . mapSecond f

We can annotate this with a partially filled out type to see what was inferred:

diagonal :: Setter _ _ _ _ -> Setter _ _ _ _ -> Setter _ _ _ _
diagonal mapFirst mapSecond = \f -> mapFirst f . mapSecond f

We can start out by filling everything in the parameters with unrelated type variables, and see what breaks:

diagonal :: Setter s t a b -> Setter s' t' a' b' -> Setter _ _ _ _ -- this no longer typechecks
diagonal mapFirst mapSecond = \f -> mapFirst f . mapSecond f

The minimum constraints we need to get this to typecheck again are:

a ~ a'
b ~ b'
s ~ t'

Unifying these variables and renaming, we have:

diagonal :: Setter x o a b -> Setter i x a b -> Setter _ _ _ _
diagonal mapFirst mapSecond = \f -> mapFirst f . mapSecond f

And we can just read off the inferred types to fill out the rest of the holes:

diagonal :: Setter x o a b -> Setter i x a b -> Setter i o a b
diagonal mapFirst mapSecond = \f -> mapFirst f . mapSecond f

I'd like to add the diagonal combinator to Control.Lens.Setter, but:

1. I don't know whether this operator already exists or is a specialization of something else in the lens library
2. I'd like for it to be an infix operator, or if named in natural language, to be something like a preposition that reads naturally in between the names of two setters. I can't think of a good name of either kind.

What do you folks think?

[phadej]

Diagonal is called Join in https://hackage.haskell.org/package/bifunctors-5.5.10/docs/Data-Bifunctor-Join.html

---

This is not "safe" composition:

{-# LANGUAGE RankNTypes #-}
import Control.Lens

setter :: Setter' Int Int
setter = id

-- setter laws are:
--
-- over s id = id
-- over s f . over s g = over s (f . g)

diagonal :: Setter x o a b -> Setter i x a b -> Setter i o a b
diagonal s1 s2 = setting $ \f -> over s1 f . over s2 f

setter2 :: Setter' Int Int
setter2 = diagonal setter setter

lhs = over setter2 (+ 1) . over setter2 (* 2) $ 1 -- = 6
rhs = over setter2 ((+ 1) . (* 2))            $ 1 -- = 7

So at best it would live in https://hackage.haskell.org/package/lens-5.0.1/docs/Control-Lens-Unsound.html

This is not a problem with Bifunctor definition as there parametricity ensures that parts are disjoint. (So both is valid traversal & setter). If we however take arbitrary Setters, that is not true anymore.

[masaeedu]

Well, not every Bifunctor is Bitraversable, so it seems to me you'd still want some analog of both for simple Bifunctors.

That said, this scheme will work for a diagonalization of anything that forms an n-ary functor in the mathematical sense, including e.g. ones found in mono-traversable (which don't actually form Bifunctors proper), or over 2/3 positions of a trifunctor, etc. So whether the general form of diagonal lives in Control.Lens.Unsound or elsewhere I believe it would be useful to have in the library.

[phadej]

Do you want

• Bifunctor analogue of both, i.e. ? :: Bifunctor p => Setter (p a a) (p b b) a b
• setter "parallel" composition, i.e. setterParComp :: Setter x o a b -> Setter i x a b -> Setter i o a b (it forms lawful setter when setters don't touch same bits, like diagonal id id example I showed)
• both?

I'm fine with any of the three. please make a PR, and try to get @ekmett to agree on a naming.

My idea of setterParComp is just saying what it is, like prismSum and lensProduct, the name which is probably unusable for you as you wish something "usable". I'm against having operator for it, it would be obscure outlier in a consistent (though large) operator soup. If there is a word which is usable as infix operator, that might work.

I don't know what would be a good name for Bifunctor both. There is both1 which is Traversable1 variant.