On Structuring Pure Functional Programs with
Monoidal Profunctors
Alexandre Garcia de Oliveira
MSFP 2022

April 2, 2022

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

1 / 38

Outline
1Introduction

2

Categorical framework
Profunctors

3

A monoid on monoidal profunctors

4

Programming examples

5

Free monoidal profunctors

6

Effectful monoidal profunctors

7

Monoidal profunctor optics

8Discussion(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

2 / 38Categorical framework

Monoidal Category

Used to reason about monoids.
Monoids give a structure with a binary operation that is associativeand has a unit.
Many monoids in a monoidal category represent a notion ofcomputation [Rivas and Jaskelioff, 2017].
This work presents another one.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

3 / 38Categorical framework

Profunctors

Definition

A profunctor generalizes the notion of function relations andbimodules [Leinster, 2003].
Lifts two functions: one ”covariantly” and the other ”contravariantly”.
Same laws as a functor.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal ProfunctorsApril 2, 2022

4 / 38Categorical framework

Profunctors

Profunctors in Haskell
From the profunctors package.
class Profunctor p where
dimap ∶∶ (a → b) → (c → d) → p b c → p a d
Satisfying:
dimap id id = id

dimap (f ○ g) (h ○ i) = dimap g h ○ dimap f i(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

5 / 38Categorical framework

Profunctors

Profunctors in Haskell

instance Profunctor (→) where
dimap ab cd bc = cd ○ bc ○ abdata SISO f g a b = SISO {unSISO ∶∶ f a → g b }instance (Functor f , Functor g) ⇒Profunctor (SISO f g) where
dimap ab cd (SISO bc) = SISO (fmap cd ○ bc ○ fmap ab)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

6 / 38Categorical framework

Profunctors

Day convolution - Profunctor case

Gives the notion of a tensor;
Desired properties to work with monoidal categories.
In the Functor case, allows to reason about monoidal (applicative)functors.
In the Profunctor case, allows to reason about monoidal profunctors.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

7 / 38Categorical framework

Profunctors

Day convolution as coends

For Functors (C small category):
XY(F ⋆ G)(S, T ) = ∫FX × GY × C(X ⊗ Y , T )(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

8 / 38Categorical framework

Profunctors

Day convolution as coends

For Prounctors (C small category):
ABCD(P ⋆ Q)(S, T ) = ∫P(A, B) × Q(C, D) × C(S, A ⊗ C) × C(B ⊗ D, T )(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

9 / 38Categorical framework

Profunctors

Day convolution datatype

data Day p q s t =∀a b c d.Day (p a b) (q c d) (s → (a, c)) ((b, d) → t)

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

10 / 38

A monoid on monoidal profunctors

A Monoid in the profunctor case

The monoidal profunctor slogan is: ”A monoid in the monoidal
category of profunctors with day convolution as its tensor.”(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

11 / 38

A monoid on monoidal profunctors

ExamplesGiven (C, ⊗, I) any monoidal category and the Hom profunctor
P(A, B) = A → B.

Relations: C = D = (N, ⩽), the category of natural numbers viewed asa poset. The Kronecker product is a monoidal profunctor in thissetting.
The Kronecker product between a matrix A p × q matrix and B is am × n matrix, is a matrix A ⊗ B with pm × qn entries given by(A ⊗ B) = aij B.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 202212 / 38

Programming examples

Monoidal profunctors in Haskell

Appears in product-profuntors as ProductProfunctor [Tom Ellis,2015], and as Monoidal in the work of Pickering, Gibbons and Wu.
class Profunctor p ⇒ MonoPro p where
mpempty ∶∶ p () ()(⋆) ∶∶ p a b → p c d → p (a, c) (b, d)Satisfying monoidal laws.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

13 / 38

Programming examples

Left identity:
dimap diag snd (mpempty ⋆ f ) = f
Right identity:
dimap diag fst (f ⋆ mpempty) = f
Associativity:
dimap α−1 α (f ⋆ (g ⋆ h)) = (f ⋆ g) ⋆ h(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

14 / 38

Programming examples

Examplesinstance MonoPro (→) where
mpempty = idf ⋆ g = λ(x, y) → (f x, g y)

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

15 / 38

Programming examples

Examplesinstance (Functor f , Applicative g) ⇒MonoPro (SISO f g) where
mpempty = SISO (λ → pure ())
SISO f ⋆ SISO g = SISO (zip ′ ○ (f ⋆ g) ○ unzip ′ )unzip ′ ∶∶ Functor f ⇒ f (a, b) → (f a, f b)
unzip ′ = (fmap fst ⋆ fmap snd) ○ diagzip ′ ∶∶ Applicative f ⇒ (f a, f b) → f (a, b)
zip ′ (fa, fb) = pure (, ) ⊗ fa ⊗ fb

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

16 / 38

Free monoidal profunctors

There is a free construction for a monoidal profunctor [Rivas andJaskelioff, 2017] [Milewski, 2017].

Prof (C op , C), when C is a small monoidal category, is monoidal with
the Day convolution ⋆ and the profunctor J as its unit, and also havebinary products and exponentials.
Least fixed point of µX .J + P ⋆ X .

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

17 / 38

Free monoidal profunctors

data FreeMP p s t where
MPempty ∶∶ t → FreeMP p s t
FreeMP ∶∶ (s → (x, z)) → ((y, w) → t)
→px y→ FreeMP p z w→ FreeMP p s t(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

18 / 38

Free monoidal profunctors

Build a free monoidal profunctor.
– compare with singleton
toFreeMP ∶∶ Profunctor p ⇒ p s t → FreeMP p s t
toFreeMP p = FreeMP diag fst p (MPempty ())(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

19 / 38

Free monoidal profunctors

Append a profunctor.
– compare with (:)
consMP ∶∶ Profunctor p ⇒ p a b→ FreeMP p s t→ FreeMP p (a, s) (b, t)
consMP pab (MPEmpty t) = FreeMP id id pab (Arr t)
consMP pab (FreeMP f g p fp) =FreeMP (id ⋆ f ) (id ⋆ g) pab (consMP p fp)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

20 / 38

Free monoidal profunctors

Evaluate a monoidal profunctor.
– avoid impredicative polymorphism
data Prof p q = Prof (∀x y.p x y → q x y)

foldFreeMP ∶∶ (Profunctor p, MonoPro q) ⇒Prof p q → FreeMP p s t → q s t
foldFreeMP (Arr t) =dimap (/_ → ()) (λ() → t) arrr
foldFreeMP (Prof h) (FreeMP f g p mp) =dimap f g ((h p) ⋆ foldFreeMP (Prof h) mp)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

21 / 38

Free monoidal profunctors

The free monoidal profunctor is a monoidal profunctor.
instance Profunctor p ⇒ MonoPro (FreeMP p) where
mpempty = MPempty ()MPempty t⋆q=dimap snd (λx → (t, x)) qq⋆ MPempty t=
dimap fst (λx → (x, t)) q(FreeMP f g p fp) ⋆ (FreeMP k l pp fq) = dimap t1 t2 t3
where
t1 = (assoc ′ ○ (f ⋆ k))
t2 = (sw ○ (l ⋆ g) ○ associnv)
t3 = (consMP p (consMP pp (fp ⋆ fq)))(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

22 / 38

Free monoidal profunctors

When p is an Arrow, FreeMp p is also an Arrow. To check this, one
needes to collapse all monoidal profunctor in this structure to obtain thesequential composition.
instance (MonoPro p, Arrow p) ⇒Category (FreeMP p) where
id = FreeMP (λx → (x, ())) fst (arr id) (MPempty ())
mp ○ mq = toFreeMP (fromFreeMP mp ○ fromFreeMP mq)
instance (MonoPro p, Arrow p) ⇒Arrow (FreeMP p) wherearr f = FreeMP (λx → (x, ())) fst (arr f ) (MPempty ())(⋆ ⋆ ⋆) = (⋆)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

23 / 38

Effectful monoidal profunctors

class Profunctor p ⇒ MonoPro p where
mpempty ∶∶ p () ()(⋆) ∶∶ p a b → p c d → p (a, c) (b, d)or,– compare with Dayclass Profunctor p ⇒ MonoPro p where
mpempty ∶∶ (s → ()) → (() → t) → p s t(⋆) ∶∶ (s → (a, c)) → ((b, d) → t) → p a b → p c d → p s t
What if we change the pure functions? (Use a Kleisli category for C).

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

24 / 38

Effectful monoidal profunctors

class Category k whereid ′ ∶∶ k a a(< . >) ∶∶ k b c → k a b → k a cclass K .Category k ⇒ CatProfunctor k p where
catdimap ∶∶ k a b → k c d → p b c → p a dclass (Category k, Profunctor p) ⇒ CatMonoPro k p ∣ p → k where
cmpunit ∶∶ k s () → k () t → p s t
mpZipWith ∶∶ k s (a, c) → k (b, d) t → p a b → p c d → p s t
lconvolve ∶∶ k s (a, c) → p a b → p c d → p s (b, d)
lconvolve f = mpZipWith f id ′rconvolve ∶∶ k (b, d) t → p a b → p c d → p (a, c) t
rconvolve g = mpZipWith id ′ gSame rules.
(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

25 / 38

Effectful monoidal profunctors

An example– lift when a b
newtype Lift t m a b = Lift {runLift ∶∶ m a → t m b }– Lift have a CatMonoPro instance– provided that there is a functioncomm ∶∶ (Monad m, Traversable m) ⇒ t m (m a) → t m a– and (t m) is a monad. Works with MaybeT Writer.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

26 / 38

Effectful monoidal profunctors

Quicksort with CatMonoProlift ′ ∶∶ Lift MaybeT (Writer [String ]) b blift ′ = Lift lift

qsort ∶∶ [String ] → MaybeT (Writer [String ]) [String ]qsort [ ] = return [ ]qsort xs = doguard (head xs ≡/ "")– effectful divide(ls, rs) ← runLift (lconvolve (Kleisli lsplit) lift ′ lift ′ ) (return xs)(ls ′ , rs ′ ) ← runKleisli ((Kleisli qsort) ⋆ (Kleisli qsort)) (ls, rs)– effectful conquer
ss ← runLift (rconvolve (Kleisli (rsplit (head xs))) lift ′ lift ′ )(return (ls ′ , rs ′ ))return ss(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

27 / 38

Effectful monoidal profunctors

Quicksort with CatMonoProlsplit ∶∶ [String ] → Writer [String ] ([String ], [String ])lsplit (z ∶ zs) = doxs ← return (filter (<z) zs)
ys ← return (filter (⩾ z) zs)
tell ["Splitting: " ++ show zs++ " into "++ show xs++ ", "++ show ys ]return (xs, ys)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

28 / 38

Effectful monoidal profunctors

rsplit ∶∶ String → ([String ], [String ]) → Writer [String ] [String ]rsplit l (xs, ys) = dotell ["Merging: " ++ show xs++ ", "++ l++ ", and "++ show ys ]return (xs ++ [l ] ++ ys)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

29 / 38

Monoidal profunctor optics

Pure functional data accessors (compositional) [Pickering, Gibbons
and Wu, 2017];
Generalize getters and setters for ADTs;
An optic is a general denotation to locate parts (whole) of a data
structure in which some action needs to be performed.
Each optic deals with different ADTs;
Lenses are to product types, prisms to sum types, traversals withtraversable containers, grates with function types, etc. Isos works
with any type but cannot do much with the shape of data.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

30 / 38

Monoidal profunctor optics

Profunctor optics
Getters s → a and setters s → b → t can be amalgamated in a single
type ∀p.c p ⇒ p a b → p s t where p is a profunctor and c is a
typeclass constraint.
When p is a profunctor, we have an iso.
When p is strong, we have a lens [O’Connor, 2015].
When p is closed, we have a grate [O’Connor, 2015].
When p is a monoidal profunctor, we get a mix of grates andtraversals.
The monoidal profunctor optic is given bytype Mono s t a b = ∀p.MonoPro p ⇒ p a b → p s t.
class Profunctor p ⇒ Closed p whereclosed ∶∶ p a b → p (x → a) (x → b)
(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

31 / 38

Monoidal profunctor optics

Some monoseach2 ∶∶ MonoPro p ⇒ p a b → p (a, a) (b, b)
each2 p = p ⋆ peach3 ∶∶ MonoPro p ⇒ p a b → p (a, a, a) (b, b, b)
each3 p = dimap flat3i flat3l (p ⋆ p ⋆ p)

convolve2 ∶∶ (Functor f , Applicative g, MonoPro p) ⇒p (f a) (g b) → p (f (a, a)) (g (b, b))
convolve2 p = dimap unzip ′ zip ′ (p ⋆ p)

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

32 / 38

Monoidal profunctor optics

foldMapOf ∶∶ Monoid r ⇒Mono s t a b → (a → r ) → s → r
foldMapOf lens f = runForget (lens (Forget f ))foldMapOf each3 ∶∶ Monoid r ⇒ (a → r ) → (a, a, a) → r(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

33 / 38

Monoidal profunctor optics

Every profunctorial optic has a van Laarhoven [O’Connor,2015], functorial
representation. For monoidal profunctors:
convolute ∶∶ (Applicative g, Functor f ) ⇒Mono s t a b → (f a → g b) → f s → g t
convolute mono f = unSISO (mono (SISO f ))Also called as a FiniteGrate by O’Connor but without the monoidal
profunctor semantics.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

34 / 38

Monoidal profunctor optics

If we specialize convolute to the identity functor f = Id to get a traversal[Kmett, 2011]:
traverseOf ∶∶ Applicative g ⇒Mono s t a b → (Id a → g b) → (Id s → g t)
traverseOf mono = convolute mono
Specializing convolute to the applicative functor g = Id gives a grate[O’Connor, 2015]:
zipFWithOf ∶∶ Functor f ⇒Mono s t a b → (f a → Id b) → (f s → Id t)
zipFWithOf mono = convolute mono

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

35 / 38Discussion

About monoidal profunctors
The Arrow interface provides the same parallel operation of a
monoidal (product) profunctor, but also provides a way to create atrivial computation basing on a pure function, and a notion ofsequential composition;
Monoidal profunctors provides the parallel composition and a trivial(unit) computation. Monoidal profunctor is, in this sense, a weaker
interface than Arrow;
Monoidal profunctors are stronger than a plain profunctor since it canlift a pure function with several parameters;
lmap ∶∶ Profunctor p ⇒ (a → b) → p b c → p a c
lmap2 ∶∶ MonoPro p ⇒ ((b, bb) → b ′ ) → p a b→ p c bb → p (a, c) b ′lmap2 f pa pc = dimap id f (pa ⋆ pc)(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

36 / 38

Discussion

About monoidal profunctors
Provides a nice way to think about optics;
Free monoidal profunctors have a proper nature to deal with parallel
computations (computations cannot interleave);
Kan Extensions can help to derive more Monoidal Profunctor
examples;
It can shine in linear typesetting, can be used to model contexts, andalso can be used to parser libraries.
Can be used to do matrix programming;
In this work, we discussed only the case when ⊗ = ×, i.e., the productcase of a monoidal profunctor. Using this with other tensors can bevery useful. Othe tensors can provide other optics (even mixed optics
with a smart ⊗ choice).
Enhance the monoidal profunctor inerface with this one.
class SemiCat p where(○) ∶∶ p a b → p b c → p a c(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

37 / 38

Discussion

Thank you for your attention.

(MSFP 2022)

On Structuring Pure Functional Programs with Monoidal Profunctors
April 2, 2022

38 / 38