Skip to content
/ scala_typeclassopedia Public
forked from lemastero/scala_typeclassopedia

Abstractions and constructions from math (Category theory, Abstract algebra) implementations in Scala, minimal description, links to good explanations, links to implementations in other FP languages: Haskell, Idris, Purescript, non FP too: Java, C++ and to formalizations in proof assistants: Coq (UniMath, HoTT book), Cubical Agda.

License

CC-BY-SA-4.0 license
0 stars 39 forks Branches Tags Activity
Star
Notifications

zhongl/scala_typeclassopedia

BranchesTags
 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

517 Commits

img

img

 
 

project

project

 
 

src

src

 
 

.gitignore

.gitignore

 
 

.travis.yml

.travis.yml

 
 

AbstractAlgebra.MD

AbstractAlgebra.MD

 
 

CONTRIBUTING.md

CONTRIBUTING.md

 
 

ComputationalTrinitarianism.MD

ComputationalTrinitarianism.MD

 
 

FunctionalDataStructures.MD

FunctionalDataStructures.MD

 
 

LICENSE

LICENSE

 
 

Optics.MD

Optics.MD

 
 

OtherEncodingsOfCT.MD

OtherEncodingsOfCT.MD

 
 

README.MD

README.MD

 
 

RecursionSchemas.MD

RecursionSchemas.MD

 
 

build.sbt

build.sbt

 
 

Repository files navigation

Build Status

Scala typeclassopedia

Abstract Algebra

Category Theory

Category Theory

Functor (Covariant Functor)

Type constructor F[_] that requires single type with function map - ability to transform its content, without changing the structure.

You can think of Functor using following intuitions:

  • containers (Id, List, Vector, Tree, Option) can apply given function to every element in the collection
  • computational context - map applies function to a value inside this effect, without changing the effect
    • Id - no effects
    • Const - always return the same value (ignore changes)
    • Option - may not have value,
    • List/Vector - may have multiple values,
    • Either/ValidatedNel/Try - may contain value or error(s)
    • Reader - require some context to be computed
    • Writer - while computing value, generate some description
    • State, IO - computing changes a state
    • Monix Task/Future/Twitter Future/Scalaz Task - needs time to be computed
    • Map - is indexed with other type (see Controversies about Map)
trait Functor[F[_]] {
  def map[A,B](a: F[A])(f: A => B): F[B]
}

If Functor satisfies first law, then it also satisfies second: (Haskell) The second Functor law is redundant - David Luposchainsky if we don't include bottom values - (Haskell) contrexample using undefined.

  • In Category Theory, functor is a mapping of:
    • objects (F[_] maps types e.g. Int to List[Int]) and
    • morphisms (if f is mapping between A and B then we can think of map(f) as mapping between F[A] and F[B]) that
    • preserves composition and identity - this is ensured by the Functor Laws

But in general, functor maps two arbitrary categories. Functor, that maps the same category to itself, is called endo functor. So strictly speaking, Functor in programming is Endofunctor in Category theory.

  • Derived methods of Functor:
def lift[A, B](f: A => B): F[A] => F[B] // lift regular function to function inside container
def fproduct[A, B](fa: F[A])(f: A => B): F[(A, B)] // zip elements with result after applying f
def as[A, B](fa: F[A], b: B): F[B] // replace every element with b
def void[A](fa: F[A]): F[Unit] // clear preserving structure
def tupleLeft[A, B](fa: F[A], b: B): F[(B, A)]
def tupleRight[A, B](fa: F[A], b: B): F[(A, B)]
def widen[A, B >: A](fa: F[A]): F[B]

Functor definition does not require any conditions on type constructor F or any other operations (unlike Applicative, Monad). Therefore pretty much everything is a Functor. Notable exceptions are:

  1. function input arguments (they are in negative position) or any input like type - see Contravariant We can define Functor only for return type - because type is in positive position.
  2. abstractions where type can be both input and output, see Invariant and blog post Rotten Bananas by Edward Kmett
  3. abstractions that behave like a Functor but not there are some controversies:

Apply

Apply is a Functor with superpower to apply function already inside container to container of arguments.

trait Apply[F[_]] extends Functor[F] {
  def ap[A, B](ff: F[A => B])(fa: F[A]): F[B]
}
def apComposition[A, B, C](fa: F[A], fab: F[A => B], fbc: F[B => C]): Boolean = {

  //        ap F[A => B]              ap F[B => C]
  // F[A] ==================> F[B] =================> F[C]
  val fb: F[B] = ap(fab)(fa)
  val left: F[C] = ap(fbc)(fb)

  val expand: (B => C) => ((A => B) => (A => C)) =
    (bc: B => C) =>
      (ab: A => B) =>
        bc compose ab

  //               map( A=>B => B=>C => A=>C )
  // F[B => C] ======================================> F[A=>B => A=>C]
  val fabac: F[(A => B) => (A => C)] = map(fbc)(expand)

  //              ap F[A=>B => A=>C]
  // F[A => B] ==============================> F[A => C]
  val fac: F[A => C] = ap(fabac)(fab)

  //           ap F[A=>C]
  // F[A] =========================> F[C]
  val right: F[C] = ap(fac)(fa)

  left == right
}
  • Derived methods (there are version defined from xyz2 until xyz22)
def apply2[A, B, Z]   (fa: F[A], fb: F[B])          (ff: F[(A,B) => Z]): F[Z]
def apply3[A, B, C, Z](fa: F[A], fb: F[B], fc: F[C])(ff: F[(A,B,C) => Z]): F[Z]
// ...

def map2[A , B, Z]  (fa: F[A], fb: F[B])          (f: (A, B) => Z):    F[Z]
def map3[A, B, C, Z](fa: F[A], fb: F[B], fc: F[C])(f: (A, B, C) => Z): F[Z]
// ...

def tuple2[A, B]   (fa: F[A], fb: F[B]):           F[(A, B)]
def tuple3[A, B, C](fa: F[A], fb: F[B], fc: F[C]): F[(A, B, C)]
// ...

def product[A,B](fa: F[A], fb: F[B]): F[(A, B)]
def flip[A, B](ff: F[A => B]): F[A] => F[B]

  • Apply was extracted from Applicative definition and usually is defined as a weaker version of Applicative that cannot put value inside effect F. So, instances for Apply are the same as for Applicative.

  • Apply can compose: Cats compose ComposedApply, Scalaz 7)

  • Resources:

Applicative (Applicative Functor)

Applicative Functor is a Functor that can:

  • apply function already inside container to container of arguments (so it is Apply)
  • put value into container (lift into effect)
trait Applicative[F[_]] extends Apply[F] {
  def pure[A](value: A): F[A] // point
}

1 identify: xs.ap(pure(identity)) == xs apply identify function lifted inside effect does nothing

def apIdentityLaw[A](fa: F[A]): Boolean = {
  val l1: F[A => A] = pure(identity[A])
  val l2: F[A] = ap(l1)(fa)

  //         ap F[identity]
  //  F[A] ==================> F[A]
  l2 == fa
}

2 homomorphism: pure(a).ap(pure(f)) == pure(f(a)) lifting value a and applying lifted function f is the same as apply function to this value and then lift result

def homomorphismLaw[A, B](ab: A => B, a: A): Boolean = {
  val fab: F[A => B] = pure(ab)
  val fa: F[A] = pure(a)

  //         F[A => B]
  // F[A] =============> F[B]
  val l: F[B] = ap(fab)(fa)

  val r: F[B] = pure(ab(a))

  l == r
}

3 interchange: pure(a).ap(ff) == ff.ap(pure(f => f(a))) where ff: F[A => B]

def interchangeLaw[A, B](fab: F[A => B], a: A): Boolean = {
  //       ap F[A => B]
  // F[A] ==============> F[B]
  val l: F[B] = ap(fab)(pure(a))

  val fabb: F[(A => B) => B] = pure((f: A => B) => f(a))

  //              ap F[(A => B) => B]
  // F[A => B] ========================> F[B]
  val r: F[B] = ap(fabb)(fab)

  l == r
}

4 map: fa.map(f) == fa.ap(pure(f))

def mapLikeDerivedLaw[A, B](f: A => B, fa: F[A]): Boolean = {
  val l: F[B] = map(fa)(f)
  val r: F[B] = ap(pure(f))(fa)
  l == r
}

  • Derived methods - see Apply

  • Applicatives can be composed (Cats compose ComposedApplicative, Scalaz 7)

  • Minimal set of methods to implement Applicative (other methods can be derived from them):

    • map2, pure
    • apply, pure

  • Resources:

    • herding cats - Applicative: (blog post)
    • FSiS 2 - Applicative type class - Michael Pilquist: (video)
    • FSiS 3 - Monad type class - Michael Pilquist: (video)
    • Cats: docs
    • Applicative programming with effects - Conor McBride, Ross Paterson (shorter) longer
    • The Essence of the Iterator Pattern - Jeremy Gibbons, Bruno C. d. S. Oliveira: (paper)
    • The Essence of the Iterator Pattern - Eric Torreborre (blog post)
    • Static analysis with Applicatives - Gergő Érdi (blog post)
    • Lifting - Tony Morris (blog post)
    • (Haskell) Abstracting with Applicatives - Gershom Bazerman (blog post)
    • (Haskell) Algebras of Applicatives - Gershom Bazerman (blog post)
    • Functional Patterns in C++, 2. Currying, Applicative - Bartosz Milewski (video)

Selective (Selective applicative functors)

"Extend the Applicative type class with a single method that makes it possible to be selective about effects."

"handle is a selective function application: you apply a handler function of type A => B when given a value of type Left(a), but can skip the handler (along with its effects) in the case of Right(b)."

Andrey Mokhov

trait Selective[F[_]] extends Applicative[F] {
  def handle[A, B](fab: F[Either[A, B]], ff: F[A => B]): F[B]
  def select[A, B, C](fab: F[Either[A, B]], fac: F[A => C], fbc: F[B => C]): F[C]
}

Monad

We add to Apply ability flatMap that can join two computations and use the output from previous computations to decide what computations to run next.

trait Monad[F[_]] extends Apply[F] {
  def pure[A](value: A): F[A]
  def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}
  • Monad Laws (Cats, Scalaz 7, Haskell Wiki):
    1. flatmap associativity: fa.flatMap(f).flatMap(g) == fa.flatMap(a => f(a).flatMap(b => g(b))
    2. left identity: pure(a).flatMap(f) == f(a)
    3. right identity: fa.flatMap(a => pure(a)) == fa
def flatMapAssociativity[A,B,C](fa: M[A], f: A => M[B], g: B => M[C]): Boolean = {
  //         flatMap(f)
  //  M[A] =============> M[B]
  val l1: M[B] = flatMap(fa)(f)
  //         flatMap(g)
  //  M[B] =============> M[C]
  val l2: M[C] = flatMap(l1)(g)

  val r1: A => M[C] = a => flatMap(f(a))(b => g(b))
  //         flatMap(f flatMap g)
  //  M[A] ======================> M[C]
  val r2: M[C] = flatMap(fa)(r1)
  l2 == r2
}

def leftIdentity[A,B,C](a: A, f: A => M[B], g: B => M[C]): Boolean = {
  //    pure
  // A =======> M[A]
  val l1: M[A] = pure(a)
  //        flatMap
  // M[A] ==========> M[B]
  val l2: M[B] = flatMap(l1)(f)

  // A =======> M[B]
  val r: M[B] = f(a)
  l2 == r
}

def rightIdentity[A,B,C](a: A, fa: M[A], g: B => M[C]): Boolean = {
  //        flatMap
  // M[A] ==========> M[A]
  val l: M[A] = flatMap(fa)(pure)
  
  val r: M[A] = fa
  l == r
}

  • Minimal set of methods to implement Monad (others can be derived using them):

    • pure, flatMap
    • pure, flatten, map
    • pure, flatten, apply
    • pure, flatten, map2

  • Derived methods:

def flatten[A](ffa: F[F[A]]): F[A]
def sequence[G[_], A](as: G[F[A]])(implicit G: Traverse[G]): F[G[A]]
def traverse[A, G[_], B](value: G[A])(f: A => F[B])(implicit G: Traverse[G]): F[G[B]]
def replicateA[A](n: Int, fa: F[A]): F[List[A]]
def unit: F[Unit] // put under effect ()
def factor[A, B](ma: F[A], mb: F[B]): F[(A, B)]

Reader

Wrapper around function from given type. Input type can be seen as some configuration required to produce result.

case class Reader[-In, +R](run: In => R) {
  def map[R2](f: R => R2): Reader[In, R2] =
    Reader(run andThen f)

  def flatMap[R2, In2 <: In](f: R => Reader[In2, R2]): Reader[In2, R2] =
    Reader(x => f(run(x)).run(x))
}

Writer

  • Resources
    • Monadic Logging and You - Martin Snyder (video)
    • The Writer Monad using Scala (example) - Tony Morris: blog post

State

Abstraction over stateful computation.

case class State[S,A](runState: S => (A,S))

is a monad:

def stateMonad[S]: Monad[State[S, ?]] = new Monad[State[S, ?]] {

  def pure[A](a: A): State[S, A] = State(s => (a, s))

  def flatMap[A, B](ma: State[S, A])(f: A => State[S, B]): State[S, B] = State[S, B](
    s => {
      val (a: A, s2: S) = ma.runState(s)
      f(a).runState(s2)
    }
  )
}

RWS Monad

Update Monad

  • Resources
    • (Haskell) Update Monads: Variation On State Monads - Chris Penner (blog post)

Logic Monad, Prompt Monad, Failure Monad

Type-Indexed Monads

ContT (Continuation Monad)

Reverse State Monad

Tardis (Bidirectional State Monad)

Dijkstra monad

trait Dijkstra[S,A] {
  def wp[Omega](f: (S,A) => Omega): S => Omega
}

is a Monad:

implicit def dijakstraMonad[S]: Monad[Dijkstra[S, ?]] = new Monad[Dijkstra[S, ?]] {
  def pure[A](a: A): Dijkstra[S,A] = new Dijkstra[S,A] {
    def wp[Omega](f: (S, A) => Omega): S => Omega =
      s => f(s,a)
  }

  def flatMap[A,B](ma: Dijkstra[S,A])(f: A => Dijkstra[S,B]): Dijkstra[S,B] =
    new Dijkstra[S,B] {
      def wp[Omega](g: (S, B) => Omega): S => Omega =
        ma.wp{ case (s,a) => f(a).wp(g)(s) }
    }
}

can be created from State:

def fromState[S,A](h: State[S,A]): Dijkstra[S,A] =
  new Dijkstra[S,A] {
    def wp[Omega](f: (S, A) => Omega): S => Omega =
      s => {
        val (a,s2) = h.runState(s)
        f(s2,a)
      }
  }

and converted to State:

def fromDijkstra[S,A](k: Dijkstra[S,A]): State[S,A] = State(
  s => k.wp{ case(s2,a) => (a,s2) }(s)
)
  • Resources
    • (Haskell) Dijkstra monads - James Cheney (blgo post)
    • Dijkstra Monads in Monadic Computation - Bart Jacobs (paper)
    • Dijkstra Monads for Free - Danel Ahman et. al. (paper)
    • Verifying Higher order Programs with the Dijkstra Monad - Nikhil Swamy, Juan Chen, Ben Livshits (paper)

Hoare Monad

  • Resources
    • (Coq) The Hoare State Monad - Wouter Swierstra (paper)

IO related monads

IO Monad

Bifunctor IO (BIO)

RIO Monad (Reader + IO)

TRIO (RIO Monad + Bifunctor IO)

Contravariant (Contravariant Functor)

Type constructor that can be contramap, so map in opposite direction.

If we imagine Functor, as abstracting over some output, then Contravariant abstract over input.

In Category Theory Contravariant Functor is a Functor from opposite category (opposite category formalization in CubicalTT).

trait Contravariant[F[_]] {
  def contramap[A, B](f: B => A): F[A] => F[B]
}

Scalaz 7, Scalaz 8, Cats, Haskell, Purescript, UniMath, nLab

1 contramap identity

//         contramap(id)
// F[A]  ================> F[A]
contramap(fa)(identity[A]) == fa

2 contravariant composition

//        contramap f
// F[A] ==============> F[B]
val fb: F[B] = contramap(fa)(f)

//        contramap g
// F[B] ===============> F[C]
val l: F[C] = contramap(fb)(g)

//        contramap (g . f)
// F[A] =====================> F[B]
val r: F[C] = contramap(fa)(f compose g)

l == r

Divide (Contravariant Apply)

trait Divide[F[_]] extends Contravariant[F] {
  def divide[A,B,C](f: A => (B,C), fb: F[B], fc: F[C]): F[A]
}
def divideComposition[A](fa1: F[A], fa2: F[A], fa3: F[A]): Boolean = {
  //                divide(delta)
  //  F[A1], F[A2] ===============> F[A12]
  val fa12: F[A] = divide(delta[A], fa1, fa2)

  //                 divide(delta)
  // F[A12], F[A3] =================> F[A123]
  val l: F[A] = divide( delta[A], fa12, fa3)


  //                divide(delta)
  //  F[A2], F[A3] ===============> F[A23]
  val fa23: F[A] = divide(delta[A], fa2, fa3)

  //                  divide(delta)
  //  F[A1], F[A23] ===============> F[A123]
  val r: F[A] = divide( delta[A], fa1, fa23 )
  
  l == r
}

This is simplified version. Proper version is shown in Haskell.

  • Derived methods:
def divide1[A1, Z]    (a1: F[A1])           (f: Z => A1): F[Z] // contramap
def divide2[A1, A2, Z](a1: F[A1], a2: F[A2])(f: Z => (A1, A2)): F[Z]
// ...
def tuple2[A1, A2]    (a1: F[A1], a2: F[A2]):            F[(A1, A2)]
def tuple3[A1, A2, A3](a1: F[A1], a2: F[A2], a3: F[A3]): F[(A1, A2, A3)]
// ...
def deriving2[A1, A2, Z](f: Z => (A1, A2))(implicit a1: F[A1], a2: F[A2]): F[Z]
def deriving3[A1, A2, A3, Z](f: Z => (A1, A2, A3))(implicit a1: F[A1], a2: F[A2], a3: F[A3]): F[Z]
// ...
  • Resources
    • (Haskell) Contravariant Functors: The Other Side of the Coin - George Wilson (video)
    • (Haskell, Category Theory) Discrimination is Wrong: Improving Productivity - Edward Kmett (video) slides pdf

Divisible (Contravariant Applicative)

trait Divisible[F[_]] extends Divide[F] {
  def conquer[A]: F[A]
}

  1. all Contravariant and Divide laws including composition divide(divide(a1, a2)(delta), a3)(delta) == divide(a1, divide(a2, a3),(delta))(delta) (see Divide law)

  2. right identity: divide(fa, conquer)(delta) == fa

def rightIdentity[A](fa: F[A]): Boolean = {
  //                 divide(delta)    
  // F[A], conquer ===============> F[A]
  val l: F[A] = divide(delta, fa, conquer[A])
  
  l == fa
}
  1. left identity: divide(conquer, fa)(delta) == fa
def leftIdentity[A](fa: F[A]): Boolean = {
  //                 divide(delta)    
  // conquer, F[A] ===============> F[A]
  val l: F[A] = divide(delta, conquer[A], fa)
  
  l == fa
}

  • Instances: Predicate, Sorting, Serializable, Pritty Printing

  • Resources

    • Cats PR #2034 explaining design choices different that in Haskell, Scalaz
    • (Haskell) Contravariant Functors: The Other Side of the Coin - George Wilson (video)
    • (Haskell, Category Theory) Discrimination is Wrong: Improving Productivity - Edward Kmett (video) slides pdf

Bifunctor

Abstracts over type constructor with 2 "holes". Represents two independent functors:

trait Bifunctor[F[_, _]] {
  def bimap[A, B, C, D](fab: F[A, B])(f: A => C, g: B => D): F[C, D]
}
  • Bifunctor Laws
  1. identity xs.bimap(identity, identity) == xs bimap with two identify function does nothing
  2. composition xs.bimap(f, h).bimap(g,i) == xs.bimap(x => g(f(x), x => h(i(x)) you can bimap using f and h and then bimap using g and i or bimap once using composition Second law is automatically fulfilled if the first law holds.
  • Alternatively can be specified by providing
def leftMap[A, B, C](fab: F[A, B])(f: A => C): F[C, B]
def rightMap[A, B, D](fab: F[A, B])(g: B => D): F[A, D]

In that case identity law must hold for both functions: 3. identity xs.leftMap(identity) == xs leftMap with identify function does nothing 4. identity xs.rightMap(identity) == xs rightMap with identify function does nothing If leftMap and rightMap and bimap are specified then additional lwa must be fullfilled: 5. xs.bimap(f, g) == xs.leftMap(f).rightMap(g)

  • Derived methods
def leftMap[A, B, C](fab: F[A, B])(f: A => C): F[C, B]
def rightMap[A, B, D](fab: F[A, B])(g: B => D): F[A, D]
def leftFunctor[X]: Functor[F[?, X]]
def rightFunctor[X]: Functor[F[X, ?]]
def umap[A, B](faa: F[A, A])(f: A => B): F[B, B]
def widen[A, B, C >: A, D >: B](fab: F[A, B]): F[C, D]

Bifunctor Join

Turn a Bifunctor with both arguments with the same type into Functor.

newtype Join p a = Join { runJoin :: p a a }

-- instance
-- Bifunctor p => Functor (Join p)

Bifunctor Wrap

Functor over second argument of a Bifunctor

newtype WrappedBifunctor p a b = WrapBifunctor { unwrapBifunctor :: p a b }

-- instance
-- Bifunctor p => Functor (WrappedBifunctor p a)

Bifunctor Flip

Swap arguments of Bifunctor

newtype Flip p a b = Flip { runFlip :: p b a }

-- instance
-- Bifunctor p => Bifunctor (Flip p)

Bifunctor Joker

Functor over second argument of Bifunctor

newtype Joker g a b = Joker { runJoker :: g b }

-- instance
-- Functor g => Bifunctor (Joker g :: * -> * -> *)
-- Functor g => Functor (Joker g a)

Bifunctor Clown

Functor over second argument of Bifunctor

newtype Clown f a b = Clown { runClown :: f a }

-- instances
-- Functor (Clown f a :: * -> *)
-- Functor f => Bifunctor (Clown f :: * -> * -> *)

Bifunctor Product

Product of two Bifunctors

data Product f g a b = Pair (f a b) (g a b)

-- instance
-- (Bifunctor f, Bifunctor g) => Bifunctor (Product f g)

Bifunctor Sum

Sum of two Bifunctors

data Sum p q a b = L2 (p a b) | R2 (q a b)

-- instance
-- (Functor f, Bifunctor p) => Functor (Tannen f p a)

Bifunctor Tannen

Compose Functor on the outside.

newtype Tannen f p a b = Tannen { runTannen :: f (p a b) }

-- instances
-- (Functor f, Bifunctor p) => Bifunctor (Tannen f p)
-- (Functor f, Bifunctor p) => Functor (Tannen f p a)

Bifunctor Biff

Compose two Functors inside Bifunctor

newtype Biff p f g a b = Biff { runBiff :: p (f a) (g b) }

-- instance
-- (Bifunctor p, Functor f, Functor g) => Bifunctor (Biff p f g)

Bitraverse

Bifoldable

Invariant (Invariant Functor, Exponential Functor)

Functor that can create covariant functor (by passing identity as g) or contravariant functor (by passing identity to f). It represent situation when given type constructor contains type on both positive and negative position (like function A => A).

trait Invariant[F[_]] {
  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}

Distributive

Traverse are composable Distributive it require only Functor (and Traverse require Applicative)

trait Distributive[F[_]] extends Functor[F] {
  def collect[G[_]:Functor,A,B](fa: G[A])(f: A => F[B]): F[G[B]]
  def distribute[G[_]:Functor,A](fa: G[F[A]]): F[G[A]]
}

Comonad

Abstraction for type with one hole that allows:

  • map over (extends Functor)
  • get current value
  • duplicate one layer of abstraction It is dual to Monad (Monad allow to put value in and collapse one layer).
trait CoflatMap[F[_]] extends Functor[F] {
  def coflatMap[A, B](fa: F[A])(f: F[A] => B): F[B]
}

trait Comonad[C[_]] extends CoflatMap[C] {
  def extract[A](ca: C[A]): A // counit
  def duplicate[A](ca: C[A]): C[C[A]] // coflatten
  def extend[A, B](ca: C[A])(f: C[A] => B): C[B] = map(duplicate(ca))(f) // coflatMap, cobind
}

If we define extract and extend:

  1. fa.extend(_.extract) == fa
  2. fa.extend(f).extract == f(fa)
  3. fa.extend(f).extend(g) == fa.extend(a => g(a.extend(f)))

If we define comonad using map, extract and duplicate: 3. fa.duplicate.extract == fa 4. fa.duplicate.map(_.extract) == fa 5. fa.duplicate.duplicate == fa.duplicate.map(_.duplicate)

And if we provide implementation for both duplicate and extend: 6. fa.extend(f) == fa.duplicate.map(f) 7. fa.duplicate == fa.extend(identity) 8. fa.map(h) == fa.extend(faInner => h(faInner.extract))

The definitions of laws in Cats src Comonad , Cats src Coflatmap and Haskell Control.Comonad.

  • Derived methods:
 def extend[A, B](ca: C[A])(f: C[A] => B): C[B] = map(duplicate(ca))(f) // coFlatMap

Method extend can be use to chain oparations on comonads - this is called coKleisli composition.

Coreader (Env comonad, Product comonad)

Wrap value of type A with some context R.

case class CoReader[R, A](extract: A, ask: R) {
  def map[B](f: A => B): CoReader[R, B] = CoReader(f(extract), ask)
  def duplicate: CoReader[R, CoReader[R, A]] = CoReader(this, ask)
}

Cowriter

It is like Writer monad, combines all logs (using Monid) when they are ready.

case class Cowriter[W, A](tell: W => A)(implicit m: Monoid[W]) {
  def extract: A = tell(m.empty)
  def duplicate: Cowriter[W, Cowriter[W, A]] = Cowriter( w1 =>
    Cowriter( w2 =>
      tell(m.append(w1, w2))
    )
  )
  def map[B](f: A => B) = Cowriter(tell andThen f)
}
  • Resources
    • Scala Comonad Tutorial, Part 1 - Rúnar Bjarnason (blog post)

Bimonad

Combine power of Monad and Comonad with additiona laws that tie together Monad and Comonad methods

trait Bimonad[T] extends Monad[T] with Comonad[T]
  • They simplify resolution of implicits for things that are Monad and Comonad

Resources:

Foldable

Given definition of foldLeft (eager, left to right0) and foldRight (lazi, right to left) provide additional way to fold Monoid.

trait Foldable[F[_]]  {
  def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B
  def foldRight[A, B](fa: F[A], z: => B)(f: (A, => B) => B): B
}
  • Laws: no. You can define condition that foldLeft and foldRight must be consistent.
  • Derived methods (are different for scalaz and Cats):
def foldMap[A, B](fa: F[A])(f: A => B)(implicit B: Monoid[B]): B
def foldM    [G[_], A, B](fa: F[A], z: B)(f: (B, A) => G[B])(implicit G: Monad[G]): G[B] // foldRightM
def foldLeftM[G[_], A, B](fa: F[A], z: B)(f: (B, A) => G[B])(implicit G: Monad[G]): G[B]
def find[A](fa: F[A])(f: A => Boolean): Option[A] // findLeft findRight
def forall[A](fa: F[A])(p: A => Boolean): Boolean // all
def exists[A](fa: F[A])(p: A => Boolean): Boolean // any
def isEmpty[A](fa: F[A]): Boolean // empty
def get[A](fa: F[A])(idx: Long): Option[A] // index
def size[A](fa: F[A]): Long // length
def toList[A](fa: F[A]): List[A]
def intercalate[A](fa: F[A], a: A)(implicit A: Monoid[A]): A
def existsM[G[_], A](fa: F[A])(p: A => G[Boolean])(implicit G: Monad[G]): G[Boolean] // anyM
def forallM[G[_], A](fa: F[A])(p: A => G[Boolean])(implicit G: Monad[G]): G[Boolean] // allM

// Cats specific
def filter_[A](fa: F[A])(p: A => Boolean): List[A]
def takeWhile_[A](fa: F[A])(p: A => Boolean): List[A]
def dropWhile_[A](fa: F[A])(p: A => Boolean): List[A]
def nonEmpty[A](fa: F[A]): Boolean
def foldMapM[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: Monad[G], B: Monoid[B]): G[B]
def traverse_[G[_], A, B](fa: F[A])(f: A => G[B])(implicit G: Applicative[G]): G[Unit]
def sequence_[G[_]: Applicative, A](fga: F[G[A]]): G[Unit]
def foldK[G[_], A](fga: F[G[A]])(implicit G: MonoidK[G]): G[A]

// scalaz specific
def filterLength[A](fa: F[A])(f: A => Boolean): Int
def maximum[A: Order](fa: F[A]): Option[A]
def maximumOf[A, B: Order](fa: F[A])(f: A => B): Option[B]
def minimum[A: Order](fa: F[A]): Option[A]
def minimumOf[A, B: Order](fa: F[A])(f: A => B): Option[B]
def splitWith[A](fa: F[A])(p: A => Boolean): List[NonEmptyList[A]]
def splitBy[A, B: Equal](fa: F[A])(f: A => B): IList[(B, NonEmptyList[A])]
def selectSplit[A](fa: F[A])(p: A => Boolean): List[NonEmptyList[A]]
def distinct[A](fa: F[A])(implicit A: Order[A]): IList[A]

Traverse

Functor with method traverse and folding functions from Foldable.

trait Traverse[F[_]] extends Functor[F] with Foldable[F] {
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]
}
def sequence[G[_]:Applicative,A](fga: F[G[A]]): G[F[A]]
def zipWithIndex[A](fa: F[A]): F[(A, Int)] // indexed
// ... other helper functions are different for scalaz and cats

SemigroupK (Plus)

Semigroup that abstracts over type constructor F. For any proper type A can produce Semigroup for F[A].

trait SemigroupK[F[_]] {
  def combineK[A](x: F[A], y: F[A]): F[A]  // plus
  def algebra[A]: Semigroup[F[A]] //  semigroup
}

  • SemigroupK can compose

  • Resources:

    • Scalaz (src)
    • Cats docs src
    • FSiS 6 - SemigroupK, MonoidK, MonadFilter, MonadCombine - Michael Pilquist (video)

MonoidK (PlusEmpty)

Monoid that abstract over type constructor F. For any proper type A can produce Monoid for F[A].

trait MonoidK[F[_]] extends SemigroupK[F] {
  def empty[A]: F[A]
  override def algebra[A]: Monoid[F[A]] // monoid
}

  • MonoidK can compose

  • Resources:

FunctorFilter

TraverseFilter

Monads not compose - solutions

Monad Transformers (OptionT EitherT ReaderT)

"Monad transformers just aren’t practical in Scala." John A De Goes

  • Resources

Extensible effects

Natural transformation (FunctionK)

Represent mappings between two functors.

trait NaturalTransf[F[_], G[_]] {
  def apply[A](fa: F[A]): G[A]
}

Free constructions

abstraction free construction
Monoid List, Vector
Functor Yoneda, Coyoneda, Density, Codensity, Right Kan Extension, Left Kan Extension, Day Convolution
Applicative FreeApplicative
Alternative Free Alternative
Monad Free Monads, Codensity, Right Kan Extension
Comonad CoFree, Density
Profunctor Profunctor CoYoneda, Profunctor Yoneda, Tambara, Pastro, Cotambara, Copastro, TambaraSum, PastroSum, CotambaraSum, CopastroSum, Closure, Environment, CofreeTraversing, FreeTraversing, Traversing
ProfunctorFunctor Profunctor CoYoneda, Profunctor Yoneda, Tambara, Pastro, Cotambara, Copastro, TambaraSum, PastroSum, CotambaraSum, CopastroSum, Closure, Environment, CofreeTraversing, FreeTraversing
ProfunctorMonad Pastro, Copastro, PastroSum, CopastroSum, Environment, FreeTraversing
ProfunctorComonad Tambara, Cotambara, TambaraSum, CotambaraSum, Closure, CofreeTraversing
Strong Tambara, Pastro, Traversing
Costrong Cotambara, Copastro
Choice TambaraSum, PastroSum
Cochoice CotambaraSum, CopastroSum, Traversing
Closed Closure, Environment
Traversing CofreeTraversing, FreeTraversing
Arrow Free Arrow

Free Applicative

  • Implementations: Scalaz 7 Haskell

  • Resources

    • Cats docs
    • Free Applicative Functors - Paolo Capriotti, Ambrus Kaposi (paper)
    • Move Over Free Monads: Make Way for Free Applicatives! - John deGoes (video)
    • Flavours of free applicative functors - Roman Cheplyaka (blog post)

Free Monads

ADT (sometimes implemented using Fix point data type) that form a Monad, without any other conditions:

sealed trait Free[F[_],A]
case class Return[F[_],A](a: A) extends Free[F,A]
case class Suspend[F[_],A](s: F[Free[F,A]]) extends Free[F,A]

Free Monad transformers

Cofree

Create comonad for any given type A. It is based on rose tree (multiple nodes, value in each node) where List is replaced with any Functor F. Functor F dedicdes how Cofree comonad is branching.

case class Cofree[A, F[_]](extract: A, sub: F[Cofree[A, F]])(implicit functor: Functor[F]) {
  def map[B](f: A => B): Cofree[B, F] = Cofree(f(extract), functor.map(sub)(_.map(f)))
  def duplicate: Cofree[Cofree[A, F], F] = Cofree(this, functor.map(sub)(_.duplicate))
  def extend[B](f: Cofree[A, F] => B): Cofree[B, F] = duplicate.map(f) // coKleisi composition
}

Free Alternative

Representable & Adjunctions

Representable

// TODO Haskell extends Distrivutive, Scalaz require F to be Functor
trait Representable[F[_], Rep] {
  def tabulate[X](f: Rep => X): F[X]
  def index[X](fx: F[X])(f: Rep): X
}

Corepresentable

Adjunction

Adjunction[F,B] spacify relation between two Functors (There is natural transformation between composition of those two functors and identity.) We say that F is left adjoint to G.

trait Adjunction[F[_], G[_]] {
  def left[A, B](f: F[A] => B): A => G[B]
  def right[A, B](f: A => G[B]): F[A] => B
}

Adjunction can be defined between Reader monad and Coreader comonad.

(Co)Yoneda & (Co)Density & Kan Extensions

Yoneda

Construction that abstract over type constructor and allow to efficiently stack computations.

In Category Theory

Yoneda Lemma states that: [C,Set](C(a,-),F) ~ Fa Set of natural transformations from C to Set of the Hom functor C(a,-) to Functor F: C -> Set is isomorphic to Fa

It is possible to formulate Yoneda Lemma in terms of Ends, and we get Ninja Yoneda Lemma: ∫ Set(C(a,x),F(x)) ~ Fa

That corresponds to:

def yoneda[R](cax: A => X, fx F[X]) ~ F[A]

trait Yoneda[F[_], A] {
  def run[R](f: A => R): F[R]
}
  • we need Functor instance for F to create instance of Yoned for F
def liftYoneda[F[_], A](fa: F[A])(implicit FunctorF: Functor[F]): Yoneda[F, A] =
  new Yoneda[F, A] {
    def run[R2](f: A => R2): F[R2] = FunctorF.map(fa)(f)
  }
  • we don't need the fact that F is a Functor to go back to F
def lowerYoneda[F[_], A](y: Yoneda[F, A]): F[A] = y.run(identity[A])
  • we can define Functor instance, without any requirement on F:
def yonedaFunctor[F[_]]: Functor[Yoneda[F, ?]] =
  new Functor[Yoneda[F, ?]] {
    def map[A, B](fa: Yoneda[F, A])(f: A => B): Yoneda[F, B] =
      new Yoneda[F, B] {
        def run[C](f2: B => C): F[C] = fa.run(f andThen f2)
      }
  }

  • Yoneda efficiently stack computations.

  • Implementations scalaz Scalaz 7, Purescript, UniMath, HoTT, nlab

  • Resources

    • https://vimeo.com/122708005
    • Free Monads and the Yoneda Lemma - Rúnar Bjarnason (blog post)
    • (Scala & Haskell) How Haskell is Changing my Brain, Yay Yoneda - Alissa Pajer (video)
    • (Haskell) Reverse Engineering Machines with the Yoneda Lemma - Dan Piponi: (blog post)
    • (Haskell) Free Monads for Less (Part 2 of 3): Yoneda - Edward Kmett (blog post)
    • Category Theory III 7.1, Natural transformations as ends - Bartosz Milewski (video)

Coyoneda

Rúnar in Free Monads and the Yoneda Lemma describes this type as a proof that: "if we have a type B, a function of type (B => A) for some type A, and a value of type F[B] for some functor F, then we certainly have a value of type F[A]"

This result from Category Theory allows us to perform Coyoneda Trick:

If we have following type:

trait Coyoneda[F[_], A] {
  type B
  def f: B => A
  def fb: F[B]
}

then type constructor F can be lifted to Coyoneda

def liftCoyoneda[F[_], A](fa: F[A]): Coyoneda[F, A]

we can map over lifted constructor F, without any requirements on F. So Coyoneda is a Free Functor:

implicit def coyoFunctor[F[_]]: Functor[Coyoneda[F, ?]] = new Functor[Coyoneda[F, ?]] {
  def map[A, AA](fa: Coyoneda[F, A])(ff: A => AA): Coyoneda[F, AA] = new Coyoneda[F, AA] {
    type B = fa.B
    def f: B => AA = fa.f andThen ff
    def fb: F[B] = fa.fb
  }
}

We even can change the oryginal type of F

def hoistCoyoneda[F[_], G[_], A, C](fab : NaturalTransf[F,G])(coyo: Coyoneda[F, A]): Coyoneda[G, A] =
  new Coyoneda[G, A] {
    type B = coyo.B
    def f: B => A = coyo.f
    def fb: G[B] = fab(coyo.fb)
  }

Finally to get back from Coyoneda fantazy land to reality of F, we need a proof that it is a Functor:

def lowerCoyoneda(implicit fun: Functor[F]): F[A]

  • Implementations: calaz 7, Haskell, nLab

  • Resources

    • loop/recur Coyoneda (video)
    • Free Monads and the Yoneda Lemma - Rúnar Bjarnason (blog post)
    • (Scala & Haskell) How Haskell is Changing my Brain, Yay Yoneda - Alissa Pajer (video)
    • (Haskell) Reverse Engineering Machines with the Yoneda Lemma - Dan Piponi: (blog post)
    • (Haskell) Free Monads for Less (Part 2 of 3): Yoneda - Edward Kmett (blog post)

Right Kan extension

trait Ran[G[_], H[_], A] {
  def runRan[B](f: A => G[B]): H[B]
}
def ranFunctor[G[_], H[_]]: Functor[Ran[G, H, ?]] =
    new Functor[Ran[G, H, ?]] {

      def map[A, B](fa: Ran[G, H, A])(f: A => B): Ran[G, H, B] =
        new Ran[G, H, B] {
          def runRan[C](f2: B => G[C]): H[C] =
            fa.runRan(f andThen f2)
        }
    }
  • We can define Monad for Ran, without any requirements on G, H. Monad generated by Ran is Codensity.
def codensityMonad[F[_], A](ran: Ran[F, F, A]): Codensity[F, A] =
  new Codensity[F, A] {
    def run[B](f: A => F[B]): F[B] = ran.runRan(f)
  }

Left Kan Extension

trait Lan[F[_], H[_], A] {
  type B
  val hb: H[B]
  def f: F[B] => A
}

Scalaz, Haskell, Purescript, nLab

  • we can define Functor for it
def lanFunctor[F[_], H[_]]: Functor[Lan[F, H, ?]] = new Functor[Lan[F, H, ?]]() {
  def map[A, X](x: Lan[F, H, A])(fax: A => X): Lan[F, H, X] = {
    new Lan[F, H, X] {
      type B = x.B
      val hb: H[B] = x.hb
      def f: F[B] => X = x.f andThen fax
    }
  }
}

Density Comonad

Density is a Comonad that is simpler that Left Kan Extension. More precisely it is comonad formed by left Kan extension of a Functor along itself.)

trait Density[F[_], Y] { self =>
  type X
  val fb: F[X]
  def f: F[X] => Y
  
  def densityToLan: Lan[F,F,Y] = new Lan[F,F,Y] {
   type B = X
   val hb: F[B] = fb
   def f: F[B] => Y = self.f
  }
}

object Density {
  def apply[F[_], A, B](kba: F[B] => A, kb: F[B]): Density[F, A] = new Density[F, A] {
    type X = B
    val fb: F[X] = kb
    def f: F[X] => A = kba
  }
}

Scalaz PR, Purescript, Haskell

Density form a Functor without any conditions on F, so it is a Free Functor. Similar like Lan.

def functorInstance[K[_]]: Functor[Density[K, ?]] = new Functor[Density[K, ?]] {
  def map[A, B](x: Density[K, A])(fab: A => B): Density[K, B] = Density[K,B,x.X](x.f andThen fab, x.fb)
}

Density is a Comonad without any conditions of F, so it is a Free Comonad.

def comonadInstance[K[_]]: Comonad[Density[K, ?]] = new Comonad[Density[K, ?]] {
  def extract[A](w: Density[K, A]): A = w.f(w.fb)
  def duplicate[A](wa: Density[K, A]): Density[K, Density[K, A]] =
    Density[K, Density[K, A], wa.X](kx => Density[K, A, wa.X](wa.f, kx), wa.fb)
  def map[A, B](x: Density[K, A])(f: A => B): Density[K, B] = x.map(f)
}

Codensity

Interface with flatMap'ish method:

trait Codensity[F[_], A] {
  def run[B](f: A => F[B]): F[B]
}

It gives us monad (without any requirement on F):

implicit def codensityMonad[G[_]]: Monad[Codensity[G, ?]] =
  new Monad[Codensity[G, ?]] {
    def map[A, B](fa: Codensity[G, A])(f: A => B): Codensity[G, B] =
      new Codensity[G, B] {
        def run[C](f2: B => G[C]): G[C] = fa.run(f andThen f2)
      }

    def unit[A](a: A): Codensity[G, A] =
      new Codensity[G, A] {
        def run[B](f: A => G[B]): G[B] = f(a)
      }

    def flatMap[A, B](c: Codensity[G, A])(f: A => Codensity[G, B]): Codensity[G, B] =
      new Codensity[G, B] {
        def run[C](f2: B => G[C]): G[C] = c.run(a => f(a).run(f2))
      }
  }

Contravariant Adjuctions & Representable

Contravariant Adjunction

Contravariant Rep

Contravariant Kan Extensions

Contravariant Yoneda

Contravariant Coyoneda

Similar a Coyoneda yet, with existenctial function running in opposite direction.

trait ContravariantCoyoneda[F[_], A] {
  type B
  val fb: F[B]
  val m: A => B


  def lowerCoyoneda(implicit CF: Contravariant[F]): F[A] = CF.contramap(fb)(m) // run
}

def liftCoyoneda[F[_], AA](fa: F[AA]): ContravariantCoyoneda[F, AA] = new ContravariantCoyoneda[F, AA] {
  type B = AA
  val fb: F[B] = fa
  val m: AA => B = identity[AA]
}

We can define Contravariant instance for Contravariant Coyoneda:

def cotraContraCoyo[F[_]] = new Contravariant[ContravariantCoyoneda[F, ?]] {
  def contramap[AA, BB](fa: ContravariantCoyoneda[F, AA])(f: BB => AA): ContravariantCoyoneda[F, BB] = new ContravariantCoyoneda[F, BB] {
    type B = fa.B
    val fb: F[B] = fa.fb
    val m: BB => B = fa.m compose f
  }
}

Contravariant Day

Invariant Day

Functor Functor (FFunctor)

Functor that works on natural transformations rather than on regular types

trait FFunctor[FF[_]] {
  def ffmap[F[_],G[_]](nat: NaturalTransf[F,G]): FF[F] => FF[G]
}

  • Laws:

    • identity: ffmap id == id
    • composition: ffmap (eta . phi) = ffmap eta . ffmap phi

  • Resources

Monad morphisms

higher kinded category theory

Monoidal Categories, Monoid Object

In Category Theory a Monoidal Category is a Category with a Bifuctor and morphisms that satisfy some laws (see gist for details).

trait MonoidalCategory[M[_, _], I] {
  val tensor: Bifunctor[M]
  val mcId: I

  def rho[A]    (mai: M[A,I]): A
  def rho_inv[A](a:   A):      M[A, I]

  def lambda[A]      (mia: M[I,A]): A
  def lambda_inv[A,B](a: A):        M[I, A]

  def alpha[A,B,C](    mabc: M[M[A,B], C]): M[A, M[B,C]]
  def alpha_inv[A,B,C](mabc: M[A, M[B,C]]): M[M[A,B], C]
}

We can create monoidal category where product (Tuple) is a bifunctor or an coproduct (Either).

Monoidal Categories are usefull if we consider category of endofunctors. If we develop concept of Monoid Object then it is possible to define Monads as Monoid Object in Monoidal Category of Endofunctors with Product as Bifunctor Applicative as Monoid Object in Monoidal Category of Endofunctors with Day convolution as Bifunctor

In category of Profunctors with Profunctor Product as Bifunctor the Monoid Ojbect is Arrow.

Cartesian Closed Category

Day Convolution

Monads are monoids in a monoidal category of endofunctors. Applicative functors are also monoids in a monoidal category of endofunctors but as a tensor is used Day convolution.

There is nice intuition for Day convolution as generalization of one of Applicative Functor methods.

  • Haskell
data Day f g a where
  Day :: forall x y. (x -> y -> a) -> f x -> g y -> Day f g a
  • Scala
trait DayConvolution[F[_], G[_], A] {
  type X
  type Y
  val fx: F[X]
  val gy: G[Y]
  def xya: (X, Y) => A
}
def day[F[_], G[_], A, B](fab: F[A => B], ga: G[A]): Day[F, G, B]
def intro1[F[_], A](fa: F[A]): Day[Id, F, A]
def intro2[F[_], A](fa: F[A]): Day[F, Id, A]
  • Day convolution can be transformed by mapping over last argument, applying natural transformation to one of type constructors, or swapping them
def map[B](f: A => B): Day[F, G, B]
def trans1[H[_]](nat: NaturalTransf[F, H]): Day[H, G, A]
def trans2[H[_]](nat: NaturalTransf[G, H]): Day[F, H, A]
def swapped: Day[G, F, A] = new Day[G, F, A]
  • There is various ways to collapse Day convolution into value in type constructor:
def elim1[F[_], A](d: Day[Id, F, A])(implicit FunF: Functor[F]): F[A]
def elim2[F[_], A](d: Day[F, Id, A])(implicit FunF: Functor[F]): F[A]
def dap[F[_], A](d: Day[F, F, A])(implicit AF: Applicative[F]): F[A]
  • We can define Functor instance without any conditions on type constructors (so it forms Functor for free like Coyoneda):
def functorDay[F[_], G[_]]: Functor[DayConvolution[F, G, ?]] = new Functor[DayConvolution[F, G, ?]] {
  def map[C, D](d: DayConvolution[F, G, C])(f: C => D): DayConvolution[F, G, D] =
    new DayConvolution[F, G, D] {
      type X = d.X
      type Y = d.Y
      val fx: F[X] = d.fx
      val gy: G[Y] = d.gy

      def xya: X => Y => D = x => y => f(d.xya(x)(y))
    }
}

  • If both type constructor are Applicative then whoe Day Convolution is applicative. Similarly it is Comonad if both type constructors are Comonads.

  • Resources

Profunctor

Profunctor abstract over

  • type constructor with two holes P[_,_]
  • operation def dimap(preA: NewA => A, postB: B => NewB): P[A, B] => P[NewA, NewB] that given P[A,B] and two functions
  • apply first preA before first type of P (ast as contravariant functor)
  • apply second postB after second type of P (act as functor)

Alternatively we can define Profunctor not using dimap but using two separate functions:

  • def lmap(f: AA => A): P[A,C] => P[AA,C] = dimap(f,identity[C])
  • def rmap(f: B => BB): P[A,B] => P[A,BB] = dimap(identity[A], f)

Profunctors in Haskell were explored by sifpe at blog A Neighborhood of Infinity in post Profunctors in Haskell Implemented in Haskell: ekmett/profunctors

trait Profunctor[F[_, _]] {
  def dimap[A, B, C, D](fab: F[A, B])(f: C => A)(g: B => D): F[C, D]
}
def lmap[A, B, C](fab: F[A, B])(f: C => A): F[C, B]
def rmap[A, B, C](fab: F[A, B])(f: B => C): F[A, C]
  • Most popular is instance for Function with 1 argument:
trait Profunctor[Function1] {
  def lmap[A,B,C](f: A => B): (B => C) => (A => C) = f andThen
  def rmap[A,B,C](f: B => C): (A => B) => (A => C) = f compose
}

Becasue Profunctors can be used as base to define Arrows therefore there are instances for Arrow like constructions like Kleisli

  • In Category Theroy: When we have Category C and D and D' the opposite category to D, then a Profunctor P is a Functor D' x C -> Set We write D -> C In category of types and functions we use only one category, so Profunctor P is C' x C => C

  • Laws Scalaz 7 Cats:

  • if we define Profunctor using dimap:
    • dimap id id == id
def dimapIdentity[A, B](p: P[A, B]): Boolean = {
  //          dimap(id, id)
  // P[A,B] ================> P[A,B]
  dimap(identity[A], identity[B])(p) == p
}
  • dimap (f . g) (h . i) == dimap g h . dimap f i
def dimapComposition[A, B, C, D, E, F](pad: P[A,D], fcb: C => B, fba: B => A, fde: D => E, fef: E => F): Boolean = {
  //          dimap B=>A D=>E
  // P[A,D] ===================> F[B,E]
  val pbe: P[B, E] = dimap(fba, fde)(pad)
  //          dimap C=>B E=>F
  // P[B,E] ====================> P[C,F]
  val l: P[C,F] = dimap(fcb, fef)(pbe)

  val fca: C => A = fba compose fcb
  val fdf: D => F = fef compose fde
  //         dimap C=>A D=> F
  // P[A,D] ===================> P[C,F]
  val r: P[C,F] = dimap(fca, fdf)(pad)
  
  l == r
}

Second law we get for free by parametricity.

  • if specify lmap or rmap
    • lmap id == id
    • rmap id == id
    • lmap (f . g) == lmap g . lmap f
    • rmap (f . g) == rmap f . rmap g

Last two laws we get for free by parametricity.

  • if specify both (in addition to law for dimap and laws for lmap:
    • dimap f g == lmap f . rmap g

Star

Lift Functor into Profunctor "forward"

case class Star[F[_],D,C](runStar: D => F[C])

If F is a Functor then Star[F, ?, ?] is a Profunctor:

def profunctor[F[_]](implicit FF: Functor[F]): Profunctor[Star[F, ?,?]] = new Profunctor[Star[F, ?, ?]] {
  def dimap[X, Y, Z, W](ab: X => Y, cd: Z => W): Star[F, Y, Z] => Star[F, X, W] = bfc =>
    Star[F,X, W]{ x =>
      val f: Y => F[Z] = bfc.runStar
      val fz: F[Z] = f(ab(x))
      FF.map(fz)(cd)
    }
}

CoStar

Lift Functor into Profunctor "backwards"

case class Costar[F[_],D,C](runCostar: F[D] => C)

If F is a Functor then Costar[F, ?, ?] is a Profunctor

def profunctor[F[_]](FF: Functor[F]): Profunctor[Costar[F, ?, ?]] = new Profunctor[Costar[F, ?, ?]] {
  def dimap[A, B, C, D](ab: A => B, cd: C => D): Costar[F, B, C] => Costar[F, A, D] = fbc =>
    Costar{ fa =>
      val v: F[B] = FF.map(fa)(ab)
      val c: C = fbc.runCostar(v)
      cd(c)
    }
}

Strong Profunctor

Profunctor with additional method first that lift profunctor so it can run on first element of tuple.

For Profunctor of functions from A to B this operation just apply function to first element of tuple.

trait StrongProfunctor[P[_, _]] extends Profunctor[P] {
  def first[X,Y,Z](pab: P[X, Y]): P[(X, Z), (Y, Z)]
}
  • Laws Haskell Cats
    1. first == dimap(swap, swap) andThen second
    2. lmap(_.1) == rmap(_.1) andThen first
    3. lmap(second f) andThen first == rmap(second f) andThen first
    4. first . first ≡ dimap assoc unassoc . first
    5. second ≡ dimap swap swap . first
    6. lmap snd ≡ rmap snd . second
    7. lmap (first f) . second ≡ rmap (first f) . second
    8. second . second ≡ dimap unassoc assoc . second

where

assoc ((a,b),c) = (a,(b,c))
unassoc (a,(b,c)) = ((a,b),c)

In Notions of Computation as Monoids by Exequiel Rivas and Mauro Jaskelioff in 7.1 there are following laws:

  1. dimap identity pi (first a) = dimap pi id a
  2. first (first a) = dimap alphaInv alpha (first a)
  3. dimap (id × f) id (first a) = dimap id (id × f) (first a)
  • Derived methods:
def second[X,Y,Z](pab: P[X, Y]): P[(Z, X), (Z, Y)]
def uncurryStrong[P[_,_],A,B,C](pa: P[A, B => C])(S: Strong[P]): P[(A,B),C]

In Purescript implementation of Strong there are some more helper methods that use Category constraint for P.

  • Most common instance is Function with one argument:
val Function1Strong = new Strong[Function1] with Function1Profunctor {
  def first[X, Y, Z](f: Function1[X, Y]): Function1[(X,Z), (Y, Z)] = { case (x,z) => (f(x), z) }
}

it is possible to define instance for Kleisli arrow

Tambara

trait Tambara[P[_,_],A,B]{
  def runTambara[C]: P[(A,C),(B,C)]
}

Tambara is a Profunctor:

trait Profunctor[Tambara[P, ?, ?]] {
  def PP: Profunctor[P]

  def dimap[X, Y, Z, W](f: X => Y, g: Z => W): Tambara[P, Y, Z] => Tambara[P, X, W] = (tp : Tambara[P, Y, Z]) => new Tambara[P, X, W]{
   
    def runTambara[C]: P[(X, C), (W, C)] = {
      val fp: P[(Y,C),(Z,C)] => P[(X, C), (W, C)] = PP.dimap(
        Function1Strong.first[X, Y, C](f),
        Function1Strong.first[Z, W, C](g)
      )
      val p: P[(Y,C),(Z,C)] = tp.runTambara[C]
      fp(p)
    }
  }
}

It is also FunctorProfunctor:

def promap[P[_, _], Q[_, _]](f: DinaturalTransformation[P, Q])(implicit PP: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => Tambara[P, A, B]], Lambda[(A,B) => Tambara[Q, A, B]]] = {
  new DinaturalTransformation[Lambda[(A,B) => Tambara[P, A, B]], Lambda[(A,B) => Tambara[Q, A, B]]] {
    def dinat[X, Y](ppp: Tambara[P, X, Y]): Tambara[Q, X, Y] = new Tambara[Q, X, Y] {
      def runTambara[C]: Q[(X, C), (Y, C)] = {
        val p: P[(X,C), (Y,C)] = ppp.runTambara
        f.dinat[(X,C), (Y,C)](ppp.runTambara)
      }
    }
  }
}

Profunctor Costrong

trait Costrong[F[_,_]] extends Profunctor[F] {
  def unfirst[A,B,D](fa: F[(A,D), (B, D)]): F[A,B]
  def unsecond[A,B,D](fa: F[(D,A),(D,B)]): F[A,B]
}

Choice Profunctor

Profunctor with additional method left that wrap both types inside Either.

trait ProChoice[P[_, _]] extends Profunctor[P] {
  def left[A,B,C](pab: P[A, B]):  P[Either[A, C], Either[B, C]]
}
  • derived method
def right[A,B,C](pab: P[A, B]): P[Either[C, A], Either[C, B]]

Extranatural Transformation

trait ExtranaturalTransformation[P[_,_],Q[_,_]]{
  def exnat[A,B](p: P[A,B]): Q[A,B]
}

Profunctor Functor

Functor (endofunctor) between two Profunctors.

It is different than regualar Functor: Functor lifts regular function to function working on type constructor: def map[A, B](f: A => B): F[A] => F[B] Profunctor lifts two regular functions to work on type constructor with two holed.

And ProfunctorFunctor lifts dinatural transformation of two Profunctors P[,] => Q[,]

operates on type constructor with one hole (F[A] => F[B]) and ProfunctorFunctor and ProfunctorFunctor map P[A,B] => Q[A,B]

in Scala 2.12 we cannot express type constructor that have hole with shape that is not sepcified)

trait ProfunctorFunctor[T[_]] {
  def promap[P[_,_], Q[_,_]](dt: DinaturalTransformation[P,Q])(implicit PP: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[P[A,B]]], Lambda[(A,B) => T[Q[A,B]]]]
}

Profunctor Monad

trait ProfunctorMonad[T[_]] extends ProfunctorFunctor[T] {
  def proreturn[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[P, Lambda[(A,B) => T[P[A,B]]]]
  def projoin[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[T[P[A,B]]]], Lambda[(A,B) => T[P[A,B]]]]
}
  • Laws:
    • promap f . proreturn == proreturn . f
    • projoin . proreturn == id
    • projoin . promap proreturn == id
    • projoin . projoin == projoin . promap projoin

Profunctor Comonad

trait ProfunctorComonad[T[_]] extends ProfunctorFunctor[T] {
  def proextract[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[P[A,B]]], P]
  def produplicate[P[_,_]](implicit P: Profunctor[P]): DinaturalTransformation[Lambda[(A,B) => T[P[A,B]]], Lambda[(A,B) => T[T[P[A,B]]]]]
}
  • Laws
    • proextract . promap f == f . proextract
    • proextract . produplicate == id
    • promap proextract . produplicate == id
    • produplicate . produplicate == promap produplicate . produplicate

Profunctor Yoneda

trait ProfunctorYoneda[P[_,_],A,B] {
  def runYoneda[X,Y](f: X => A, g: B => Y): P[X,Y]
}

is a Profunctor for free, because we can define:

def dimap[AA, BB](l: AA => A, r: B => BB): ProfunctorYoneda[P, AA, BB] = new ProfunctorYoneda[P, AA, BB] {
  def runYoneda[X, Y](l2: X => AA, r2: BB => Y): P[X, Y] = {
    val f1: X => A = l compose l2
    val f2: B => Y = r2 compose r
    self.runYoneda(f1, f2)
  }
}

Profunctor CoYoneda

trait ProfunctorCoyoneda[P[_,_],A,B] {
  type X
  type Y
  def f1: A => X
  def f2: Y => B
  def pxy: P[X,Y]
}

helper constructor:

def apply[XX,YY,P[_,_],A,B](ax: A => XX, yb: YY => B, p: P[XX,YY]): ProfunctorCoyoneda[P,A,B] = new ProfunctorCoyoneda[P,A,B] {
  type X = XX
  type Y = YY
  def f1: A => X = ax
  def f2: Y => B = yb
  def pxy: P[X,Y] = p
}

ProfunctorCoyoneda is a Profunctor for free:

def dimap[C, W](l: C => A, r: B => W): ProfunctorCoyoneda[P, C, W] =
  ProfunctorCoyoneda[X, Y, P, C, W](f1 compose l, r compose f2, pxy)

Profunctor Ran

Profunctor Codensity

Profunctor Adjunction

Profunctor Rep

  • TODO Corepresentable, Corep, Prep, Coprep

  • Implementations: Haskell

Procompose

In general Profunctors should have straightforward way to compose them as we have the same category in definition. But to be faithfull with Category Theory definition, Profunctor Composition is defined using exitential types:

trait Procompose[P[_,_],Q[_,_],D,C] {
  type X
  val p: P[X,C]
  val q: Q[D,X]
}

ProductProfunctor

A generalization of Profunctor by adding Applicative superpowers to output. Documentation of tomjaguarpaw/product-profunctors on Hackage is excelent.

class Profunctor p => ProductProfunctor p where
  purePP :: b -> p a b
  (****) :: p a (b -> c) -> p a b -> p a c
  empty  :: p () ()
  (***!) :: p a b -> p a' b' -> p (a, a') (b, b')

(***$) :: ProductProfunctor p => (b -> c) -> p a b -> p a c
  • utility methods from p0 to p62
p3 :: forall p a0 a1 a2 b0 b1 b2. ProductProfunctor p => (p a0 b0, p a1 b1, p a2 b2) -> p (a0, a1, a2) (b0, b1, b2)

from to pT1 to pT62

pT3 :: forall p a0 a1 a2 b0 b1 b2. ProductProfunctor p => T3 (p a0 b0) (p a1 b1) (p a2 b2) -> p (T3 a0 a1 a2) (T3 b0 b1 b2)

SumProfunctor

class Profunctor p => SumProfunctor p where
  (+++!) :: p a b -> p a' b' -> p (Either a a') (Either b b')

list :: (ProductProfunctor p, SumProfunctor p) => p a b -> p [a] [b]

ProfunctorEnd

class Profunctor p => ProfunctorEnd p where
  end :: p a a

instance ProfunctorEnd (->) where
  end = id

Arrows

Category

Abstraction for operations that can be composed and that provide no-op (id).

trait Compose[F[_, _]] {
  def compose[A, B, C](f: F[B, C], g: F[A, B]): F[A, C] // alias <<<
}

trait Category[F[_, _]] extends Compose[F] {
  def id[A]: F[A, A]
}

Arrow

CommutativeArrow

Arrow Choice

Arrow Apply, Arrow Monad

Arrow Loop

Arrow Zero

Free Arrow

Kleisli

Cokleisli

  • Cats

BiArrow

  • Resources:
    • There and back again: arrows for invertible programming - Artem Alimarine , Sjaak Smetsers , Arjen Weelden , Marko Eekelen , Rinus Plasmeijer (paper)
    • (Haskell) BiArrow

BiKleisli

Adjoint Triples

Dinatural Transformation

Dinatural Transformation is a function that change one Profunctor P into another one Q without modifying the content. It is equivalent to Natural Transformation between two Functors (but for Profunctors).

trait DinaturalTransformation[P[_,_],Q[_,_]]{
  def dinat[A](p: P[A,A]): Q[A,A]
}

Limits

Cone

Cocone

Diagonal Functor

Limit

Colimit

Ends & Coends

Ends can be seen as infinite product. End corresponds to forall so polymorphic function:

// P is Profunctor

trait End[P[_,_]] {
  def run[A]: P[A,A]
}

Coend can be seen as infinite coproduct (sum). Coends corresponds to exists

data Coend p = forall x. Coend p x x

Comma categories, Slice category

  • Resources
    • (Theory) Pointwise Kan Extensions - Bartosz Milewski (blog post)
    • (Theory) Slice and comma categories 1 - TheCatsters (video)
    • (Theory) Slice and comma categories 2 - TheCatsters (video)
    • (Theory) Overcategories aka Comma Categories - MathProofsable (video)
    • (Theory) Abstract and Concrete Categories The Joy of Cats - Jiri Adamek, Horst Herrlich, George E. Strecker (book)
    • (Theory) Functorial Semantics of Algebraic Theories and Some Algebraic Problems in the context of Functorial Semantics of Algebraic Theories - F. William Lawvere - TAC Reprints (book)
    • (Theory) Computational Category Theory - D.E. Rydeheard, R.M. Burstall (book)
    • (Theory) comma category - nLab

Align

ADT (Algebra of types)

  • Resources
    • Haskell wiki ADT
    • Simple Algebraic Data Types - Bartosz Milewski blog post
    • Category Theory 5.2: Algebraic data types - Bartosz Milewski video
    • Counting type inhabitants - Alexander Konovalov blog post

Unit

Type that has only one element

Void

Type that has no elements. In Category Theory - Initial Object

Sum (Coproduct)

Type represents either one or another element. In set theory: disjoint union in Category theory: coproduct (sum).

Product

Type represents combination of two types. In Set theory cartesian product, in Category Theory product.

These

Type that represents both sum and product (Non exclusive two values):

Tuple(a,b) => a * b Eiter(a,b) => a + b These(a,b) => (a + b) + a*b

sealed trait These[A,B]
case class This[A, B](a: A) extends These[A,B]
case class That[A,B](b: B) extends These[A,B]
case class Those[A,B](a: A, b: B) extends These[A,B]
  • There is many abstractions that can be implemented for this data type

Implementations Scalaz Haskell

Chronicle Monad

Implementations: Cats MTL Haskell

Resources:

Unfoldable

Implementations:

Resources:

Andrey Mokhov Task

"computes the value of a key k, in a side-effect-free way, using a callback of type k → f v to find the values of its dependencies"

type Task c k v = forall f. c f => (k -> f v) -> k -> Maybe (f v)

Resources:

Cayley representations

"The Cayley representation theorem (CRT): every group is isomorphic to a group of permutations" Can be extended to monoids and defined monoidal category of endofunctor

In FP the CRT is optimisation by change of representation:

  • CRT for List monoid - difference lists
  • CRT for monads - Codensity monad
  • CRT for applicatives - NoCaM 5.4
  • CRT for arrows - ???

Resources:

  • Notions of Computation as Monoids (extended version) - Exequiel Rivas, Mauro Jaskelioff (paper)

Difference lists

  • List with concatenation and empty list is monoid. W optimize list concatenation (that is slow) by representing list as function (difference list):
type Elist[A] = List[A] => List[A]

EList is isomorphic to List:

def rep[A](xs: List[A]): Elist[A] = ys => xs ++ ys
def abs[A](xs: Elist[A]): List[A] = xs(Nil)

We can concatenate EList's efficiently and at the end get to the List back.

  • Cayley Theorem can be define for general Monoid:
trait CayleyTheoremForMonoid[M[_]] extends MonoidK[M] {
  type MonoidEndomorphism[A] = M[A] => M[A]
  def rep[A](xs: M[A]): MonoidEndomorphism[A] = ys => combineK(xs, ys)
  def abs[A](xs: MonoidEndomorphism[A]): M[A] = xs(empty)
}

Resources:

  • (Haskell) Using Difference Lists - geophf blog post
  • (Haskell) keepEquals with Difference Lists - geophf blog post
  • (Haskell) A novel representation of lists and its application to the function "reverse" - John Hughes

Double Cayley Representation

"optimises both left-nested sums and left-nested products"

Resources:

  • A Unified View of Monadic and Applicative Non-determinism - Exequiel Rivas, Mauro Jaskeliof, Tom Schrijvers (paper)

Transducers

Clojure transducers expressed using types.

type Reducer a r = r -> a -> r
type Transducer a b = forall r . Reducer a r -> Reducer b r

Resources:

  • (Haskell) Understanding Clojure transducers through types - Franklin Chen (blog post)
  • (Haskell) Transducers are monoid homomorphisms - Oleksandr Manzyuk (blog post)
  • (Haskell) Transducers, Mappers and Reducers - giuliohome (blog post)

Relative monads

Monads thats wokrs on different categories.

Resources:

  • (Type Theory) Monads Need Not Be Endofunctors - Thorsten Altenkirch, James Chapman, Tarmo Uustalu (paper), (code)

Commutative

For many standard abstractions we can add restriction to be commutative.

Implementations: Commutative Semigroup ekmett/abelian
Commutative Monoid ekmett/abelian
Commutative Apply Cats src Cats laws
Commutative Applicative Cats src Cats laws ekmett/abelian
Commutative FlatMap Cats src Cats laws
Commutative Monad Cats src Cats laws
Commutative Free Monads ekmett/abelian
Commutative Monad Transformers ekmett/abelian
Commutative Comonads ekmett/abelian

Resources:

  • (Haskell) Haskell Live-Coding, Session 1, Commutativity - Edward Kmett (video)
  • Are there any interesting commutative monads in Haskell? SO
  • The Commutativity monad (blog post) reddit

Resource About Category Theory

Functor Oriented Programming

Resources:

About

Abstractions and constructions from math (Category theory, Abstract algebra) implementations in Scala, minimal description, links to good explanations, links to implementations in other FP languages: Haskell, Idris, Purescript, non FP too: Java, C++ and to formalizations in proof assistants: Coq (UniMath, HoTT book), Cubical Agda.

Resources

Readme

License

CC-BY-SA-4.0 license
Activity

Stars

0 stars

Watchers

2 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

No packages published

Languages

  • Scala 100.0%