Folds, Scans, and Moore Machines as Monoidal
Profunctor Homomorphisms
Alexandre Garcia de Oliveira
MSFP 2024 - Tallinn, Estonia

July 8, 2024

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

1 / 24

Outline

1

Introduction

2

Folds and Scans

3

Monoidal Profunctors

4

The connection

5Conclusion(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

2 / 24

Introduction

The ideaThis paper is a theoretical application of monoidal profunctors, sinceevery key idea depends on it.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

3 / 24

Introduction

The ideaThis paper is a theoretical application of monoidal profunctors, since
every key idea depends on it.
Functional programming always relies on mathematical laws todescribe, for example, that an evaluation of an expression iswell-behaved.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

3 / 24

Introduction

The ideaThis paper is a theoretical application of monoidal profunctors, since
every key idea depends on it.
Functional programming always relies on mathematical laws todescribe, for example, that an evaluation of an expression iswell-behaved.
For example, a map over a list needs to preserve composition, and if
we map the identity function, nothing happens.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

3 / 24Introduction

The ideaThis paper is a theoretical application of monoidal profunctors, since
every key idea depends on it.
Functional programming always relies on mathematical laws todescribe, for example, that an evaluation of an expression iswell-behaved.
For example, a map over a list needs to preserve composition, and if
we map the identity function, nothing happens.
With monads, when chaining multiple functions with bind, the way
we group the functions does not affect the result. Also, if we have amonadic value and bind it to the return function, the result is thesame as the original monadic value.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

3 / 24

Introduction

Map for Lists Law in Haskell

Identity:

map id xs ≡ xs

Preserves Composition:map (f ○ g) xs ≡ map f (map g xs)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

4 / 24

Introduction

Monad Laws in Haskell

Left identity: return a >>= k ≡ k a
Right identity: m >>= return ≡ m
Associativity: (m >>= k) >>= h ≡ m >>= (λx → k x >>= h)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

5 / 24

Introduction

Functor laws

The law for lists generalizes to every Functor instance.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

6 / 24

Introduction

Functor laws

The law for lists generalizes to every Functor instance.
Identity:
fmap id xs ≡ xs

Preserves Composition:

fmap (f ○ g) xs ≡ fmap f (fmap g xs)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

6 / 24

Introduction

Monoidal Category laws
A monoidal category is a sextuple (C, ⊗, I, α, ρ, λ) where
C is a category;⊗ ∶ C × C → C is a bifunctor;
I is an object of C called unit;ρA ∶ A ⊗ I → A, λA ∶ I ⊗ A → A and αABC ∶ (A ⊗ B) ⊗ C → A ⊗ (B ⊗ C)
are three natural isomorphisms such that the diagrams below
commute.
A ⊗ (B ⊗ (C ⊗ D)) oO(A ⊗ B) ⊗ (C ⊗ D) oαα((A ⊗ B) ⊗ C) ⊗ D
Oid⊗αα⊗id

A ⊗ ((B ⊗ C) ⊗ D) oA ⊗ (I ⊗ B)
id⊗λ(MSFP 2024 - Tallinn, Estonia)(A ⊗ (B ⊗ C)) ⊗ Dα/ (A ⊗ I) ⊗ Bα&x

A ⊗ B.

ρ⊗id

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

7 / 24

Introduction

Monoidal Category laws

A monoid in a monoidal category C is a tuple (M, e, m) where M is anobject of C, e ∶ I → M is the unit morphism and m ∶ M ⊗ M → M is themultiplication morphism, satisfying
Right unit: m ○ (id ⊗ e) = ρM
Left unit: m ○ (e ⊗ id) = λM

Associativity: m ○ (m ⊗ id) = m ○ (id ⊗ m) ○ αM

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

8 / 24

Folds and Scans

Law for folds(Fusion law) foldl op e ○ map f = foldl (λs a → op s (f a)) e(Parallel-bifold law)bifoldl f g (e, u) (zip as bs) = (foldl f e as, foldl g u bs)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

9 / 24

Folds and Scans

Definition of bifoldl

bifoldl ∶∶ (c → a → c) → (d → b → d) → (c, d) → [(a, b)] → (c, d)bifoldl f g (c, d) [ ] = (c, d)bifoldl f g (c, d) ((a, b) ∶ xs) = bifoldl f g (f c a, g d b) xs(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

10 / 24

Folds and Scans

Abstracting the Pattern

The first law represents the naturality condition of a naturaltransformation between two profunctors.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

11 / 24

Folds and Scans

Abstracting the Pattern

The first law represents the naturality condition of a naturaltransformation between two profunctors.
The second law derives from a homomorphism that preserves thestructure between two monoidal profunctors.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal ProfunctorJulyHomomorphisms
8, 2024

11 / 24

Monoidal Profunctors

Monoidal Profunctor in Haskell

class Profunctor p ⇒ MonoPro p where
mpempty ∶∶ p () ()(⋆) ∶∶ p a b → p c d → p (a, c) (b, d)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

12 / 24

Monoidal Profunctors

Monoidal Profunctor in Haskell

class Profunctor p ⇒ MonoPro p where
mpempty ∶∶ p () ()(⋆) ∶∶ p a b → p c d → p (a, c) (b, d)
Left identity: dimap diagr snd (mpempty ⋆ f ) = f
Right identity: dimap diagl fst (f ⋆ mpempty) = f
Associativity: dimap α−1 α (f ⋆ (g ⋆ h)) = (f ⋆ g) ⋆ h(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

12 / 24

Monoidal Profunctors

First example

instance MonoPro (→) where
mpempty = λ() → ()f ⋆ g = λ(a, b) → (f a, g b)

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

13 / 24

Monoidal Profunctors

Second example

data Moore a b = Moore b (a → Moore a b)

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

14 / 24

Monoidal Profunctors

Second example

data Moore a b = Moore b (a → Moore a b)

instance Profunctor Moore where
dimap f g (Moore c bm) = Moore (g c) (dimap f g ○ bm ○ f )instance MonoPro Moore where
mpempty = Moore () (/_ → mpempty)(Moore b am) ⋆ (Moore d cm) =Moore (b, d) (λ(a, c) → am a ⋆ cm c)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

14 / 24

Monoidal Profunctors

Third example

data SISO f g a b = SISO {unSISO ∶∶ f a → g b }(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

15 / 24

Monoidal Profunctors

Third example

data 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)
instance (Functor f , Applicative g) ⇒ MonoPro (SISO f g) where
mpempty = SISO (λ → pure ())
SISO f ⋆ SISO g = SISO (zip ′ ○ (f ⋆ g) ○ unzip ′ )(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

15 / 24

The connection

Moore machines from coalgebras

data MooreCoalg s a b = MooreCoalg (s → b) (s → a → s)

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal ProfunctorJulyHomomorphisms
8, 2024

16 / 24

The connection

Moore machines from coalgebras

data MooreCoalg s a b = MooreCoalg (s → b) (s → a → s)buildMoore ∶∶ MooreCoalg s a b → s → Moore a bbuildMoore (MooreCoalg out next) s =Moore (out s) (buildMoore (MooreCoalg out next) ○ next s)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

16 / 24

The connection

Moore machines and folds

foldl ∶∶ (s → a → s) → s → [a ] → s(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

17 / 24

The connection

Moore machines and folds

foldl ∶∶ (s → a → s) → s → [a ] → s
Expand: ofoldl ∶∶ (s → a → s) → s → (s → b) → [a ] → b(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

17 / 24

The connection

Moore machines and folds

foldl ∶∶ (s → a → s) → s → [a ] → s
Expand: ofoldl ∶∶ (s → a → s) → s → (s → b) → [a ] → b
Use Moore: mfoldl ∶∶ Moore a b → [a ] → b(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

17 / 24

The connection

Moore machines and folds

foldl ∶∶ (s → a → s) → s → [a ] → s
Expand: ofoldl ∶∶ (s → a → s) → s → (s → b) → [a ] → b
Use Moore: mfoldl ∶∶ Moore a b → [a ] → b
Pack into SISO (f a → g b):
mfoldl ∶∶ Moore a b → SISO [ ] Identity a b(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

17 / 24

The connection

A natural transformation emerges

mfoldl is a natural transformation: for every h ∶∶ a → b, i ∶∶ c → d thefollowing diagram commutes.
Moore b c
mfoldl

Fold b c(MSFP 2024 - Tallinn, Estonia)

dimap h i

/ Moore a ddimap h imfoldl/ Fold a dFolds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

18 / 24

The connection

Monoidal profunctor homomorphism

mfoldl is a monoidal homomorphism between the profunctors Moore
and SISO [ ] Identity.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

19 / 24

The connection

Monoidal profunctor homomorphism

mfoldl is a monoidal homomorphism between the profunctors Moore
and SISO [ ] Identity.
mfoldl preserves unit mpempty: mfoldl mpempty = mpempty(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

19 / 24

The connection

Monoidal profunctor homomorphism

mfoldl is a monoidal homomorphism between the profunctors Mooreand SISO [ ] Identity.
mfoldl preserves unit mpempty: mfoldl mpempty = mpempty
mfoldl preserves the monoidal profunctor multiplication ⋆:mfoldl (m ⋆ n) = mfoldl m ⋆ mfoldl n. The lhs is the parallel
composition of Moore machines, the rhs is the same composition in aSISO.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

19 / 24

The connection

Laws and monoidal profunctor homomorphism
Naturality, gives us the foldl fusion law:foldl op e ○ map g = foldl (λs a → op s (g a)) e. This is a special caseof the naturality condition: dimap g id ○ mfoldl = mfoldl ○ dimap g id.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

20 / 24

The connection

Laws and monoidal profunctor homomorphism
Naturality, gives us the foldl fusion law:foldl op e ○ map g = foldl (λs a → op s (g a)) e. This is a special caseof the naturality condition: dimap g id ○ mfoldl = mfoldl ○ dimap g id.
The preservation of identity tells us that folding over a list of () is just().

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

20 / 24

The connection

Laws and monoidal profunctor homomorphism
Naturality, gives us the foldl fusion law:foldl op e ○ map g = foldl (λs a → op s (g a)) e. This is a special caseof the naturality condition: dimap g id ○ mfoldl = mfoldl ○ dimap g id.
The preservation of identity tells us that folding over a list of () is just().
The preservation of monoidal multiplication tells us thatfoldl (curry (lmap (λ((a, b), (c, d)) → ((a, c), (b, d))) (uncurry f ⋆uncurry g))) (e, u) (zip as bs) ≡ (foldl f e as, foldl g u bs).

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

20 / 24

The connection

Laws and monoidal profunctor homomorphism
Naturality, gives us the foldl fusion law:foldl op e ○ map g = foldl (λs a → op s (g a)) e. This is a special caseof the naturality condition: dimap g id ○ mfoldl = mfoldl ○ dimap g id.
The preservation of identity tells us that folding over a list of () is just().
The preservation of monoidal multiplication tells us thatfoldl (curry (lmap (λ((a, b), (c, d)) → ((a, c), (b, d))) (uncurry f ⋆uncurry g))) (e, u) (zip as bs) ≡ (foldl f e as, foldl g u bs).
Or using bifoldl:bifoldl f g (e, u) (zip as bs) = (foldl f e as, foldl g u bs)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

20 / 24

The connection

The same is valid for scans

type Scan a b = SISO [ ] ZipNonEmpty a b
mscanl ∶∶ Moore a b → Scan a bmscanl m = SISO (λas → ZipNonEmpty (runMoore m as))(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

21 / 24

The connection

data NonEmpty a = a ⊳ [a ]data ZipNonEmpty a = ZipNonEmpty {unzipne ∶∶ NonEmpty a }deriving Showinstance Functor ZipNonEmpty wherefmap f (ZipNonEmpty (a ⊳ as)) =ZipNonEmpty ((f a) ⊳ fmap f as)
instance Applicative ZipNonEmpty wherepure a = ZipNonEmpty (a ⊳ repeat a)(ZipNonEmpty (f ⊳ fs)) ⊗ (ZipNonEmpty (x ⊳ xs))
= ZipNonEmpty ((f x) ⊳ zipWith ($) fs xs)(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

22 / 24

Conclusion

Contributions

Investigating Moore type and SISO as instances of monoidal
profunctors has provided valuable insights..

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

23 / 24

Conclusion

Contributions

Investigating Moore type and SISO as instances of monoidal
profunctors has provided valuable insights..
Establishing a significant mathematical connection: a naturaltransformation links Moore machines with folds and scans, and thistransformation preserves the monoidal profunctor operations.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

23 / 24

Conclusion

Contributions

Investigating Moore type and SISO as instances of monoidal
profunctors has provided valuable insights..
Establishing a significant mathematical connection: a naturaltransformation links Moore machines with folds and scans, and thistransformation preserves the monoidal profunctor operations.
Laws in the monoidal profunctor domain directly translate to laws
governing folds and scans.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 202423 / 24

Conclusion

Contributions

Investigating Moore type and SISO as instances of monoidal
profunctors has provided valuable insights..
Establishing a significant mathematical connection: a naturaltransformation links Moore machines with folds and scans, and thistransformation preserves the monoidal profunctor operations.
Laws in the monoidal profunctor domain directly translate to laws
governing folds and scans.
Applying this pattern of reasoning can help identify lawful
computations using monoidal profunctors.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms8, 2024

23 / 24

Conclusion

Paper and Future Work

Provide comprehensive proofs for all claims made.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

24 / 24

Conclusion

Paper and Future Work

Provide comprehensive proofs for all claims made.
Include detailed examples to illustrate the rules in their final form.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

24 / 24

Conclusion

Paper and Future Work

Provide comprehensive proofs for all claims made.
Include detailed examples to illustrate the rules in their final form.
Definitions of the structures presented.

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

24 / 24

Conclusion

Paper and Future Work

Provide comprehensive proofs for all claims made.
Include detailed examples to illustrate the rules in their final form.
Definitions of the structures presented.
Explore whether other monoidal profunctors yield similar results.
Unfolds? Traversals?

(MSFP 2024 - Tallinn, Estonia)

Folds, Scans, and Moore Machines as Monoidal Profunctor
JulyHomomorphisms
8, 2024

24 / 24