Terms and concepts.

Natural Transformation

A natural transformation is a mapping between functors that preserves the structure of the underlying categories. — Bartosz Milewski from Understanding Yoneda

This is a case where definitions are confusing, but the actual thing is quite simple in practice. Let's try that out in Scala using the Functors List and Option.


_17
val someString: Option[String] = Some("foo")
_17
val noneString: Option[String] = None
_17
_17
// We can intuitively think of Option as being a List of 0 or 1 elements, so the
_17
// natural transformation is trivial (note: I'm intentionally avoiding the use
_17
// of Scala's own .toList):
_17
def optionToList[A](a: Option[A]): List[A] =
_17
a.map(x => List(x)).getOrElse(List.empty[A])
_17
_17
optionToList(someString)
_17
//=> res: List[String] = List(foo)
_17
_17
optionToList(noneString)
_17
//=> res: List[String] = List()
_17
_17
optionToList(None)
_17
//=> res: List[Nothing] = List()

Isomorphism

In mathematics, an isomorphism (from the Greek: isos "equal", and morphe "shape") is a homomorphism (or more generally a morphism) that admits an inverse. Two mathematical objects are isomorphic if an isomorphism exists between them. — Wikipedia

Now the Scala in which we'll describe the world's most trivial isomorphism:


_17
// These two objects are isomorphic because a morphism (i.e. function) exists
_17
// that maps each to the other.
_17
val nameAge = ("foo", 42)
_17
val ageName = (42, "foo")
_17
_17
def tuple2Iso[A, B](p: (A, B)): (B, A) = (p._2, p._1)
_17
_17
// A => B
_17
tuple2Iso(nameAge) == ageName
_17
//=> true
_17
_17
// B => A
_17
tuple2Iso(ageName) == nameAge
_17
//=> true
_17
_17
tuple2Iso(tuple2Iso(nameAge)) == nameAge
_17
//=> true

Domain and Codomain

Domains come from set theory, and represent the set of input values for a function, while codomains represent the set of output values. Therefore, a function is the mapping between its domain and codomain.

In programming, types and domains are related but not quite the same. Domains are strictly related to functions, while a type specifies a set of values.

Existential types

Read Existential type on the HaskellWiki.

Existential types provide a way of baking the generics into a type instead of explicitly declaring them. Consider the ultra-contrived example where we have a type Things which contains a list of stuff whose type we don't care about because the only operation we want to perform on it is to count how many there are.


_10
case class Things[A](list: List[A])
_10
val intThings: Things[Int] = Things(List(1, 2, 3))
_10
def count[A](ts: Things[A]) = ts.list.size
_10
count(intThings)
_10
//=> 3

Rank-1 Polymorphic Function

An example based on Higher-Rank Polymorphism in Scala:


_10
def r1[A](f: A => A, a: A): A = f(a)
_10
r1({ i: Int => i * i }, 10)
_10
// res4: Int = 100

Rank-2 Polymorphic Function

Again from Higher-Rank Polymorphism in Scala:


_10
trait ~>[F[_],G[_]] {
_10
def apply[A](a: F[A]): G[A]
_10
}

Parametricity

captures the intuition that all instances of a polymorphic function act the same way — Wikipedia

Partial Function

A function which is not defined for some inputs.

Total Function

A function which is defined for all inputs, as opposed to a partial function.

Extensionality and Intensionality

In logic, extensionality, or extensional equality, refers to principles that judge objects to be equal if they have the same external properties. It stands in contrast to the concept of intensionality, which is concerned with whether the internal definitions of objects are the same. — Wikipedia


_12
f :: Int -> Int
_12
f x = x + x + x
_12
_12
g :: Int -> Int
_12
g x = x * 3
_12
_12
-- f and g are extensionally equal but not intensionally equal.
_12
_12
h :: Int -> Int
_12
h x = x + x + x
_12
_12
-- f and h are intensionally equal.