GitPlanet

Cheap and reliable Node.js hosting starts at $3/month, and $1/month static HTML hosting

Created with love in Canada, visit hostnodejs.com today

Feel like to post an Ad? Learn Details
All Projects → lemastero → Scala_typeclassopedia

lemastero / Scala_typeclassopedia

Licence: cc-by-sa-4.0
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.

Programming Languages

scala
5932 projects

Labels

functional-programmingpatternscategory-theoryabstraction

Projects that are alternatives of or similar to Scala typeclassopedia

Plt
λΠ Programming Language Theory
Stars: ✭ 4,609 (+1263.61%)
Mutual labels:  category-theory, functional-programming
Fundamental Haskell
Fundamental Haskell book, to the point terse statements on Haskell, Category theory, and related fields. Encyclopedic pocketbook of meaning. Zen kōan-like meditations of understanding. For quick or memory curve spaced repetition learning.
Stars: ✭ 88 (-73.96%)
Mutual labels:  category-theory, functional-programming
Bow
🏹 Bow is a cross-platform library for Typed Functional Programming in Swift
Stars: ✭ 538 (+59.17%)
Mutual labels:  category-theory, functional-programming
Fp Resources
Functional programming great resources
Stars: ✭ 369 (+9.17%)
Mutual labels:  category-theory, functional-programming
Macroid
A modular functional UI language for Android
Stars: ✭ 537 (+58.88%)
Mutual labels:  abstraction, functional-programming
Category Theory Programmers
Category theory in the context of (functional) programming
Stars: ✭ 465 (+37.57%)
Mutual labels:  category-theory, functional-programming
Milewski Ctfp Pdf
Bartosz Milewski's 'Category Theory for Programmers' unofficial PDF and LaTeX source
Stars: ✭ 9,037 (+2573.67%)
Mutual labels:  category-theory, functional-programming
Arrow
Λrrow - Functional companion to Kotlin's Standard Library
Stars: ✭ 4,771 (+1311.54%)
Mutual labels:  category-theory, functional-programming
Cql
Categorical Query Language IDE
Stars: ✭ 196 (-42.01%)
Mutual labels:  category-theory, functional-programming
Functional Examples
Examples with Functional JavaScript, following Professor Frisby's course
Stars: ✭ 179 (-47.04%)
Mutual labels:  category-theory, functional-programming
Fp Core.rs
A library for functional programming in Rust
Stars: ✭ 772 (+128.4%)
Mutual labels:  category-theory, functional-programming
React Best Practices
A comprehensive reference guide to kickstart your React architecting career!
Stars: ✭ 566 (+67.46%)
Mutual labels:  patterns, functional-programming
Naive functional programming
A naive approach to functional programming using TypeScript
Stars: ✭ 129 (-61.83%)
Mutual labels:  category-theory, functional-programming
Dunai
Classic and Arrowized Functional Reactive Programming, Reactive Programming, and Stream programming, all via Monadic Stream Functions
Stars: ✭ 115 (-65.98%)
Mutual labels:  abstraction, functional-programming
Zio Prelude
A lightweight, distinctly Scala take on functional abstractions, with tight ZIO integration
Stars: ✭ 267 (-21.01%)
Mutual labels:  category-theory, functional-programming
Prelude Ts
Functional programming, immutable collections and FP constructs for typescript and javascript
Stars: ✭ 315 (-6.8%)
Mutual labels:  functional-programming
Here Be Dragons
An Intellij/Android Studio plugin to help visualise side effects in your code.
Stars: ✭ 325 (-3.85%)
Mutual labels:  functional-programming
Functional Fortran
Functional programming for modern Fortran
Stars: ✭ 311 (-7.99%)
Mutual labels:  functional-programming
Quack
🐤 A multi-paradigm programming language with gradual and duck typing that targets PHP and JS
Stars: ✭ 309 (-8.58%)
Mutual labels:  functional-programming
Gubrak
⚙️ Golang functional utility library with syntactic sugar. It's like lodash, but for Go
Stars: ✭ 329 (-2.66%)
Mutual labels:  functional-programming
View All Similar Projects ➔

Build Status Scala Steward badge

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:

    • (Haskell) Typeclassopedia - Applicative
    • (Haskell) Applicative Functors - Łukasz Marchewka (video)
    • FSiS 2 - Applicative type class - Michael Pilquist (video)
    • FSiS 3 - Monad type class - Michael Pilquist (video)
    • Cats: docs
    • (Haskell) Applicative programming with effects - Conor McBride, Ross Paterson (shorter) longer
    • (Haskell) The Essence of the Iterator Pattern - Jeremy Gibbons, Bruno C. d. S. Oliveira: (paper)
    • The Essence of the Iterator Pattern - Eric Torreborre (blog post)
    • herding cats - Applicative: (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)

IO that abstract over input, output and potential error. Below implementation based on simplified ZIO from John A De Goes tweet:

case class BIO[R, E, A](run: R => Either[E, A]) {
  def map[B](f: A => B): BIO[R, E, B] =
    BIO(r => run(r).map(f))

  def flatMap[R1 <: R, E1 >: E, B](f: A => BIO[R1, E1, B]): BIO[R1, E1, B] =
    BIO(r => run(r).flatMap(a => f(a).run(r)))
}

Classic IO is a Profunctor, for Bifunctor IO one can define also instance of Bifunctor

def zioFunctor[R,E]: Functor[BIO[R,E,*]] = new Functor[BIO[R,E,*]] {
  def map[A, B](fa: BIO[R, E, A])(f: A => B): BIO[R, E, B] = fa.map(f)
}

trait BIOMonad[R,E] extends Monad[BIO[R,E,*]] {
  def pure[A](a: A): BIO[R, E, A] = BIO(_ => Right(a))
  def flatMap[A, B](fa: BIO[R, E, A])(f: A => BIO[R, E, B]): BIO[R, E, B] = fa.flatMap(f)
}

def bioMonad[R,E]: Monad[BIO[R,E,*]] = new BIOMonad[R,E] {}

def bioContravariant[E,A]: Contravariant[BIO[*, E, A]] = new Contravariant[BIO[*,E,A]] {
  def contramap[R, RR](fa: BIO[R, E, A])(f: RR => R): BIO[RR, E, A] =
    BIO{ rr => fa.run(f(rr)) }
}

def bioProfunctor[E]: Profunctor[BIO[*,E,*]] = new Profunctor[BIO[*, E, *]] {
  def dimap[RR, R, A, AA](f: RR => R, g: A => AA): BIO[R, E, A] => BIO[RR, E, AA] = fa =>
    BIO{ rr => fa.map(g).run(f(rr)) }
}

def bioBifunctor[R]: Bifunctor[BIO[R, *, *]] = new Bifunctor[BIO[R,*,*]] {
  def bimap[E, EE, A, AA](f: E => EE, g: A => AA): BIO[R, E, A] => BIO[R, EE, AA] = fa =>
    BIO{ rr =>
      fa.run(rr) match {
        case Right(a) => Right(g(a))
        case Left(b) => Left(f(b))
      }
    }
}

RIO Monad (Reader + IO)

TRIO (RIO Monad + Bifunctor IO)

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]]
}

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

Comma categories, Slice category

  • Verified implementations: idris-ct Comma Category, idris-ct Over Category, idris-ct Under 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

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:

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)

Disintegrate

Resources:

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:

Abstractions for abstractions

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].