Scala typeclassopedia
classDiagram
Functor~F~ <|-- Apply~F~
Apply <|-- FlatMap~F~
Functor <|-- Traverse~F~
Foldable~F~ <|-- Traverse
FlatMap~F~ <|-- Monad~F~
Apply~F~ <|-- Applicative~F~
Apply <|-- CoflatMap~F~
CoflatMap <|-- Comonad~F~
Applicative <|-- Selective~F~
Selective <|-- Monad
Applicative <|-- Alternative~F~
MonoidK~F~ <|-- Alternative
Applicative <|-- ApplicativeError~F~
ApplicativeError <|-- MonadError~F~
Monad <|-- MonadError
Monad <|-- Bimonad~F~
Comonad <|-- Bimonad
class Functor {
) map(F[A], A => B): F[B]
}
class Foldable {
) foldLeft(F[A], B, Tuple2[B,A] => B): B
}
class Traverse {
) traverse(F[A], A => G[B]): G[F[B]]
}
class Apply {
) ap(F[A], F[A => B]): F[B]
) map2(Tuple2[A,B] => C, F[A], F[B]): F[C]
}
class Applicative {
) pure(A): F[A]
}
class Selective {
) select(F[Either[A,B]], F[A=>B]): F[B]
}
class FlatMap {
) flatmap(F[A], A => F[B]): F[B]
}
class Monad {
) flatten(F[F[A]]): F[A]
}
class ApplicativeError {
) raiseError(E): F[A]
}
class CoflatMap {
) extend(F[A], F[A] => B): F[B]
}
class Comonad {
) extract(W[A]): A
}
class MonoidK {
) empty(): F[A]
) combine(F[A], F[A]): F[A]
}
class Alternative {
) some(F[A]): F[NonEmptyList[A]]
) many(F[A]): F[List[A]]
}
-
Base abstractions: Functor, Apply, Applicative, Monad, Contravariant, Comonad, Foldable, Bifunctor, Arrow, Coyoneda
-
Covariant Functors: Functor, Apply, Applicative, Selective
-
Monads: Reader, Writer, State, RWS Monad, Update Monad, Logic Monad, Prompt Monad, Failure Monad, ContT (Continuation Monad), Reverse State Monad, Tardis (Bidirectional State Monad), Chronicle Monad, Bimonad, Dijkstra monad, Hoare Monad
-
Monads generalizations: Indexed Monads, SuperMonads
-
IO related monads: IO, Bifunctor IO (BIO), RIO Monad (Reader + IO), TRIO (RIO Monad + Bifunctor IO)
-
Contravariant functors: Contravariant, Divide (Contravariant Apply), Divisible (Contravariant Applicative)
-
Contravariant Adjuctions & Representable: Contravariant Adjunction, Contravariant Rep
-
Contravariant Kan Extensions: Contravariant Yoneda, Contravariant Coyoneda, Contravariant Day, Invariant Day
-
Invariant Functors: Invariant (Invariant Functor, Exponential Functor), Invariant Day
classDiagram
Bifoldable~P[+_,+_]~ <|-- Bitraverse~P[+_,+_]~
Bifunctor~P[+_,+_]~ <|-- Bitraverse
Bifunctor <|-- Biapply~P[+_,+_]~
Biapply <|-- Biapplicative~P[+_,+_]~
Functor~F[+_]~ <|-- Bifunctor
Functor <|-- Bifunctor
Functor <|-- Profunctor~P[-_,+_]~
Bifunctor <|-- Zivariant~Z[-_,+_,+_]~
Profunctor <|-- Zivariant
class Functor {
) map(F[A], A => B): F[B]
}
class Profunctor {
) dimap(AA => A, B => BB): P[A,B] => P[AA,BB]
}
class Bifunctor {
) bimap(A => AA, B => BB): P[A,B] => P[AA,BB]
}
class Bifoldable {
) bifoldLeft(F[A,B], C, (C,A) => C, (C,B) => C): C
}
class Bitraverse {
) bitraverse[G: Applicative](F[A,B], A=>G[C], B => G[D]): G[F[C,D]]
}
class Biapply {
) biApply(F[A,B], F[A=>AA,B=>BB]): F[AA,BB]
}
class Biapplicative {
) bipure(a: A, b: B): F[A,B]
}
class Zivariant {
) zimap(AA => A, B => BB, C => CC): P[A,B,C] => P[AA,BB,CC]
}
-
Bifunctors: Bifunctor, Join, Wrap, Flip, Joker, Clown, Product, Bifunctor Sum, Bifunctor Tannen, Bifunctor Biff, Bitraverse, Bifoldable,
-
Comonads: Comonad, Coreader (Env comonad, Product comonad), Cowriter, Cofree, Cokleisli, Bimonad
-
Traversing Folding Filtering: Monoid, Foldable, Traverse, Bitraverse, Bifoldable, FunctorFilter, TraverseFilter, Distributive, Cofree Traverse
-
Monads not compose - solutions: Monad Transformers, Free Monads, Tagless Final, Extensible effects
-
Free constructions, Free Applicative, Free Monads, Cofree, Free Alternative, Free Arrow, Free Monad transformers, Cofree Traverse
-
Representable & Adjunctions: Representable, Corepresentable, Adjunction, Adjoint Triples
classDiagram
Ran~G[_], H[_], A~ <|-- Yoneda~H[_], A~
Lan~G[_], H[_], A~ <|-- CoYoneda~H[_], A~
Ran <|-- Codensity~G[_], A~
Lan <|-- Density~G[_], A~
class Ran {
// Right Kan Extension
) run[B](A => G[B]): H[B]
}
class Yoneda {
) run[B](A => B): H[R]
}
class Codensity {
) run[B](A => G[B]): G[B]
}
class Lan {
// Left Kan Extension
fz: H[Z]
run: G[Z] => A
}
class CoYoneda {
fz: H[Z]
run: Z => A
}
class Density {
fz: G[Z]
run: G[Z] => A
}
class Day~G[_], H[_], A~ {
// Day convolution
gb: G[Z]
hb: H[X]
) run: (Z,X) => A
}
-
(Co)Yoneda & (Co)Density & Kan Extensions, Yoneda, Coyoneda, Right Kan extension, Left Kan Extension, Density Comonad, Codensity, Day Convolution
-
Profunctors: Profunctor, Star, CoStar, Strong Profunctor, Tambara, Choice Profunctor, Extranatural Transformation, Profunctor Functor, Profunctor Monad, Profunctor Comonad, Procompose, ProductProfunctor, SumProfunctor
-
Profunctor Adjuctions & Representable: Profunctor Adjunction, Profunctor Rep
-
Profunctor Kan Extensions: Profunctor Yoneda, Profunctor CoYoneda, Profunctor Ran, Profunctor Codensity
classDiagram
Functor~F[+_]~ <|-- Bifunctor~F[+_,+_]~
Functor <|-- Bifunctor
Functor <|-- Profunctor~F[-_,+_]~
Contravariant~F[-_]~ <|-- Profunctor
Semicategory~F[-_,+_]~ <|-- Category~F[-_,+_]~
Category <|-- Arrow~F[-_,+_]~
Bifunctor <|-- Zivariant~F[-_,+_,+_]~
Profunctor <|-- Zivariant
Profunctor <|-- Strong~F[-_,+_]~
Strong -- Arrow
Arrow <|-- ArrowApply~F[-_,+_]~
Arrow <|-- CommutativeArrow~F[-_,+_]~
Arrow <|-- ArrowLoop~F[-_,+_]~
Profunctor <|-- Choice~F[-_,+_]~
Arrow <|-- ArrowZero~F[-_,+_]~
Arrow <|-- ArrowChoice~F[-_,+_]~
Choice <|-- ArrowChoice
class Functor {
) map(F[A], A => B): F[B]
}
class Contravariant {
) contramap(F[A], B => A): F[B]
}
class Semicategory {
) compose[A,B,C](F[B,C], F[A,B]): F[A,C]
}
class Category {
) id[A]: F[A,A]
}
class Profunctor {
) dimap(AA => A, B => BB): P[A,B] => P[AA,BB]
}
class Bifunctor {
) bimap(A => AA, B => BB): P[A,B] => P[AA,BB]
}
class Zivariant {
) zimap(AA => A, B => BB, C => CC): P[A,B,C] => P[AA,BB,CC]
}
class Strong {
) first(P[A,B]): P[(A,C), (B,C)]
}
class Choice {
) left(P[A,B]): P[Either[A, C], Either[B, C]]
}
class Arrow {
) arr(A => B): F[A, B]
}
class ArrowZero {
) zeroArr(): P[A,B]
}
class ArrowApply {
) app(P[P[B,C],B]): C
}
class ArrowApply {
) app(P[P[B,C],B]): C
}
class ArrowLoop {
) loop(P[(B,D), (C,D)]: P[B,C]
}
-
Arrows: Category, Arrow, Commutative Arrow, Arrow Choice, Arrow Apply, Arrow Monad, Arrow Loop, Arrow Zero, Free Arrow, Kleisli, Cokleisli, BiArrow, BiKleisli
-
Cayley representations: Difference Lists, Codensity, Double Cayley Representation
Types | Logic | Category Theory | Homotopy Theory |
---|---|---|---|
Void | false | initial object | empty space |
Unit | true | terminal object | singleton |
Sum (Coproduct) Eiter[A,B] | A v B disjunction | coproduct | coproduct space |
Product (A,B) | A ∧ B conjunction | product | product space |
A => B | A => B implication | exponential object | singleton |
A => Void | negation | exp. obj. into initial obj. |
-
Higher kinded & exotic abstractions: Natural transformation (FunctionK), Monoidal Category, Monoid Object, Cartesian Closed Category, Day Convolution, Functor Functor (FFunctor), Monad morphisms, higher kinded category theory, SemigroupK (Plus), MonoidK (PlusEmpty), Dinatural Transformation, Ends & Coends, Align, Task, Transducers, Relative monads, Disintegrate
-
Limits: Cone, Cocone, Diagonal Functor, Limit, Colimit, Ends & Coends
-
Topoi: Subobject classifier, Topos
-
Other Encodings of Category Theory: data-category by Sjoerd Visscher, Formalizations of Category Theory in proof assistants (Coq)
Resources covering topics about FP and category theory in great details:
- "Red Book" - Functional Programming in Scala - Paul Chiusano and Rúnar Bjarnason Best book about FP in Scala. I have bought it for myself and higly recommend it. Worth reading, doing exercises and re-reading.
- Category Theory for Programmers - Bartosz Milewski the best book about this subject. Blog posts and video lectures Part 1, Part II, Part III
- (Haskell) Typeclassopedia wiki in Haskell about abstractions from category theory used by Haskell programmers - excellent resource.
- Agda formalizations: 1Lab, agda-unimath, agda/cubical, agda/agda-categories
- Seven Sketches in Compositionality: An Invitation to Applied Category Theory - Brendan Fong, David I Spivak book about Applied Category Theory branch of mathematics that use mathematics from category theory and apply it in different subjects like engineering. The video lectures based on the book by the authors.
- (Haskell) Haskell libraries containing abstractions from category theory written by Edward Kmett: Profunctors, Bifunctors, Comonad, free, adjunctions, Kan extensions, invariant, distributive, transformers, semigroupoids. This is how all of this was started :) Some of them were already moved into Haskell standard library e.g. Data.Functor.Contravariant
- zio-prelude modern look at abstractions from category theory, more modular and expressive
- (Kotlin) Patterns from Category Theory in Kotlin
- (Idris) statebox/idris-ct encoding of abstractions & formal verification in Idris 2
- Functional Structures in Scala - Michael Pilquist (video playlist): workshop on implementating FP constructions with usage examples and great insights about Scala and FP.
- Applied functional type theory - Sergei Winitzki (video playlist)
- Series of blog posts by Eugene Yokota (@eed3si9n): herding cats and learning Scalaz Easy to understand examples, clear explanations, many insights from Haskell papers and literature.
- Examples in scalaz repository Learning Scalaz is probably the best documentation for Scalaz.
- Documentation for Cats (runnable online version for older Cats version on ScalaExercises), summary
- channingwalton/typeclassopedia implementation of Haskell Typeclassopedia by Channing Walton, (blog post)
- Notes on Category Theory in Scala 3 (Dotty) - Juan Pablo Romero Méndez (blog post)
- Scala Type-class Hierarchy - Tony Morris (blog post) (traits for all cathegory theory constructions with exotic ones like
ComonadHoist
)