These are terms and concepts that I found unfamiliar the first time I encountered them. In most cases I’ll provide a brief definition or example with a link to a more complete definition. This is a work in progress.
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.
val someString: Option[String] = Some("foo")
val noneString: Option[String] = None
// We can intuitively think of Option as being a List of 0 or 1 elements, so the
// natural transformation is trivial (note: I'm intentionally avoiding the use
// of Scala's own .toList):
def optionToList[A](a: Option[A]): List[A] =
a.map(x => List(x)).getOrElse(List.empty[A])
optionToList(someString)
//=> res: List[String] = List(foo)
optionToList(noneString)
//=> res: List[String] = List()
optionToList(None)
//=> res: List[Nothing] = List()
Thus, optionToList is a natural transformation from Option to List. Note
that a natural transformation does not exist from List to Option.
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 isomophism:
// These two objects are isomorphic because a morphism (i.e. function) exists
// that maps each to the other.
val nameAge = ("foo", 42)
val ageName = (42, "foo")
def tuple2Iso[A, B](p: (A, B)): (B, A) = (p._2, p._1)
// A => B
tuple2Iso(nameAge) == ageName
//=> true
// B => A
tuple2Iso(ageName) == nameAge
//=> true
tuple2Iso(tuple2Iso(nameAge)) == nameAge
//=> true
Another resource on Isomorphisms in Scalaz: learning Scalaz — Isomorphisms
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.
In the context of functions, we can say that types are used to represent a given function’s domain and codomain.
For an interesting expansion of this concept, see slides from the Age is not an int talk. From that talk, here’s some very brief reasoning on why you want your types to semantically restrict domains:
In java.lang: not a good start
public interface Comparable{
public int compareTo(T o);
}
Representing a 3-valued type with a 2³² valued one
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.
// Without existential types
case class Things[A](list: List[A])
val intThings: Things[Int] = Things(List(1, 2, 3))
def count[A](ts: Things[A]) = ts.list.size
count(intThings)
//=> 3
Notice how we had to specify a type A on
count even though we didn’t actually care about it? Also,
the type of intThings was Things[Int],
though we could have used Things[_] to indicate we don’t
care, or even better just let its type be inferred. But that’s not the point.
Now let’s use existential types to bake A into
Things since we don’t care.
case class Things(list: List[A] forSome { type A })
def count(ts: Things) = ts.list.size
val someThings = Things(List("apathetic", "types"))
count(someThings)
//=> 2
Existential types let us drop the type annotation on count! Note, there’s a
shorthand way of expressing this:
case class Things(list: List[_])
Existential types can also rely on upper or lower bounds.
// Let's make Things only take Seqs while using Existential types shorthand in
// our upper bound
case class SeqThings(list: List[A] forSome { type A <: Seq[_] })
// Strings are Seqs
val stringThings = SeqThings(List("foo", "bar"))
// As are Lists of course
val listThings = SeqThings(List(List(1, 2), List(3)))
// Nope!
val intThings = SeqThings(List(1, 2, 3))
// <console>:9: error: type mismatch;
// found : Int(3)
// required: Seq[_]
// val intThings = SeqThings(List(1, 2, 3))
// ^
Note: Scala does not have existential types apart from Any (according to
Rúnar Bjarnason who mentions this
in his FP is terrible talk).
Rank-1 Polymorphic Function
An example based on Higher-Rank Polymorphism in Scala:
def r1[A](f: A => A, a: A): A = f(a)
r1({ i: Int => i * i }, 10)
// res4: Int = 100
Rank-2 Polymorphic Function
Again from Higher-Rank Polymorphism in Scala:
Scala doesn’t have rank-n types, so we need to rely on a workaround:
trait ~>[F[_],G[_]] {
def apply[A](a: F[A]): G[A]
}
Read the post to see how the ~> trait can be used to achieve rank-n types.
Another resource describing Haskell’s support is Higher rank types.
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
f :: Int -> Int
f x = x + x + x
g :: Int -> Int
g x = x * 3
f and g are extensionally equal, but
not intensionally equal.
h :: Int -> Int
h x = x + x + x
f and h are intensionally equal.