Let's meet the charming fold family
Today we will meet an amazing family: the fold
functions!
The well known foldRight
Lists is one of the first data structure every developer/computer scientist meet in her/his journey into programming:
sealed abstract class List[+A]
final case object Nil extends List[Nothing]
final case class Cons[+A](head: A, tail: List[A]) extends List[A]
It means means values of type List[A]
can be of (only) two forms:
- either
Nil
- or
Cons(head, tail)
for some valueshead
of typeA
andtail
of typeList[A]
For example we can define the following lists:
val empty : List[Int] = Nil
val l1 : List[Int] = Cons(61, Nil)
val l2 : List[Int] = Cons(34, Cons(61, Nil))
val l3 : List[String] = Cons("a", Cons("b", Cons("c", Nil)))
In addition, Nil
and Cons
can be seen as constants and functions returning List[A]
:
def nil[A]: List[A] = Nil
def cons[A](head: A, tail: List[A]): Lis[A] = Cons(head, tail)
The fold function, often called foldRight
, answers the question:
What would have happened if, instead of having used
Nil
andCons
in the construction of a listl:List[A]
, we would have used another constantz:T
and another functionf:(A, T) => T
for some typeT
?
Let’s illustrate this using the previous examples:
val empty : Int = 0 // z = 0
val v1 : Int = max(61, 0) // z = 0, f = max
val v2 : Int = mult(34, mult(61, 1)) // z = 1, f = mult
val v3 : String = concat("a", concat("b", concat("c", "")))
-- z = "", f = concat
The definition of foldRight
illustrates well the transformation process. It deconstructs the list l:List[A]
and replace Nil
by z
and Cons
by f
:
def foldList[A,T](z: T, f: (A,T) => T): List[A] => T = {
def transform(l: List[A]): T =
l match {
case Nil => z
case Cons(head, tail) =>
val transformedTail = transform(tail)
f(head, transformedTail)
}
transform _
}
The simple cases: Enum Types
fold
functions can be defined for a wide range of data structures. As a first example, let’s take this type:
sealed abstract class SingletonType
final case object SingleValue extends SingletonType
The type SingletonType
admits one and only one value: SingleValue
. Folding over SingletonType
means,
replacing SingleValue
by a constant z:T
for some type T
:
def foldSingletonType[T](z:T): SingletonType => T = {
def transform(v: SingletonType): T =
v match {
case SingleValue => z
}
transform _
}
While SingletonType
has only one value, the type Boolean
have exactly two values True
and False
:
sealed abstract class Boolean
final case object True extends Boolean
final case object False extends Boolean
So folding over Boolean
s mean, given a type T
and two constants tt:T
and ff:T
, replacing True
by tt
and False
by ff
:
def foldBoolean[T](tt:T, ff:T): Boolean => T = {
def transform(v: Boolean): T =
v match {
case True => tt
case False => ff
}
transform _
}
And so on for every enum type.
Beyond enums
You may start the see general process. If values of type C
are build using constructors (Nil
and Cons[A]
for List[A]
,
SingleValue
for SingletonType
, True
and False
for Boolean
), then folding is all about transforming values of type C
into another type T
by replacing each constructor of C
by a constant or function on T
of the same shape. Let’s consider
the type Either[A,B]
:
sealed abstract class Either[A,B]
final case class Left[A,B](value: A) extends Either[A,B]
final case class Right[A,B](value: B) extends Either[A,B]
To transform values of type Either[A,B]
into T
we need two functions on T
:
Left
being of typeA => Either[A,B]
we need a functionf: A => T
.Right
being of typeB => Either[A,B]
we need a functiong: B => T
.
Then we can operate the transformation:
def foldEither[A,B,T](f: A => T, g: B => T): Either[A,B] => T = {
def transform(v: Either[A,B]): T =
v match {
case Left(a) => f(a)
case Right(b) => g(b)
}
transform _
}
Recursive Types
Folding over recursive types obey the previous rules. Recursion is handled by transforming sub-terms first. Let’s consider the type of binary trees:
sealed abstract class Tree[+A]
final case object Empty extends Tree[Nothing]
final case class Node[+A](value:A, left: Tree[A], right: Tree[A]) extends Tree[A]
To transform values of type Tree[A]
into T
we need:
Empty
being a constant of typeTree[A]
, we need a constantz:T
.Node
being a function of type(A, Tree[A], Tree[A]) => Tree[A]
we need a functionf: (A, T, T) => T
. Note how all occurrences ofTree[A]
have been replaced byT
in the type.
Then we can operate the transformation:
def foldTree[A,T](z: T, f: (A, T, T) => T): Tree[A] => T = {
def transform(v: Tree[A]): T =
v match {
case Empty => z
case Node(a,l,r) =>
val g: T = transform(l) // Transforming sub-term l
val d: T = transform(r) // Transforming sub-term r
f(a,g,d)
}
transform _
}
Generalized Algebraic Data Types (GADT)
Instead of giving a formal definition of what Generalized Algebraic Data Types i will show you some examples.
Type Equalities
Consider the type:
sealed abstract class EmptyOrSingleton[A]
final case object SingleValueIfAisInt extends EmptyOrSingleton[Int]
This type looks very similar to SingletonType
but, while SingleValue
was always a value of SingletonType
,
SingleValueIfAisInt
is only a value of EmptyOrSingleton[Int]
, i.e. when A
is Int
. So what happens to
EmptyOrSingleton[A]
when A
is not Int
? Then there is no constructor for EmptyOrSingleton[A]
so no value
for SingletonIfInt[A]
(excluding null
which we will pretend no to exist).
GADTs are very useful to encode predicates over types. Imagine you have a value v:EmptyOrSingleton[A]
for
some type A
(remember we pretend null
does not exist). What could you say about A
? The only way to get
a value of type EmptyOrSingleton[A]
is through SingleValueIfAisInt
. Thus v
is SingleValueIfAisInt
which is of type EmptyOrSingleton[Int]
so is v
. We can conclude that A
is actually Int
. Not convinced?
Let A
be String
, can you build a value of type EmptyOrSingleton[String]
without using null
? Try it.
To find how to fold EmptyOrSingleton[A]
into T
, let’s apply the technique we used in the previous sections.
EmptyOrSingleton[A]
has only one constructor, SingleValueIfAisInt
, so we need a constant z:T
. But
SingleValueIfAisInt
is not of type EmptyOrSingleton[A]
but EmptyOrSingleton[Int]
. The argument A
matters
so let T
depend on A
: we want to transform values of type EmptyOrSingleton[A]
into T[A]
.
SingleValueIfAisInt
being of typeEmptyOrSingleton[Int]
we need a constantz:T[Int]
Then we can operate the transformation:
def foldEmptyOrSingleton[A, T[_]](z: T[Int]): EmptyOrSingleton[A] => T[A] = {
def transform(v: EmptyOrSingleton[A]): T[A] =
v match {
case SingleValueIfAisInt => z // Because we know A = Int
}
transform _
}
foldEmptyOrSingleton
means that, for some T[_]
, if you have a value z:T[Int]
then you can transform any value
EmptyOrSingleton[A]
into T[A]
. For example, let’s take
type T[X] = X =:= Int
val z:T[Int] = implicitly[Int =:= Int]
Then foldEmptyOrSingleton[A,T](z)
gives us, for any value v:EmptyOrSingleton[A]
a proof that A =:= Int
. Another
important use case is asserting type equality:
sealed abstract class Eq[A,B]
final case class Refl[X]() extends Eq[X,X]
Any non-null value v:Eq[A,B]
must be a Refl[X]() : Eq[X,X]
for some X
, then Eq[A,B] = Eq[X,X]
proving that
A = X = B
. To transform a value of type Eq[A,B]
into T[A,B]
we need:
Refl[X]()
is essentially a constant of typeEq[X,X]
for all typeX
(note: Scala write this type[X]Eq[X,X]
). We need a constantz:T[X,X]
for all typeX
(so the type[X]T[X,X]
). Scala does not support transparent higher-ranked types, we need to emulate them with atrait
:
trait ElimRefl[T[_,_]] {
def apply[X]: T[X,X]
}
Then we could have hoped to be able to operate the transformation like previous section. But given a value v:Eq[A,B]
,
convincing Scala that A = B
is a bit tough. Instead we can write the fold
as a method:
sealed abstract class Eq[A,B] {
def fold[T[_,_]](z: ElimRefl[T]): T[A,B]
}
final case class Refl[X]() extends Eq[X,X] {
def fold[T[_,_]](z: ElimRefl[T]): T[X,X] = z[X]
}
def foldEq[A, B, T[_,_]](z: ElimRefl[T]): Eq[A,B] => T[A,B] =
(v:Eq[A,B]) => v.fold[T](z)
Ingenious definition of T[_,_]
leads to interesting results:
trait C[X]
type T1[A,B] = C[A] =:= C[B]
val z1: ElimRefl[T1] =
new ElimRefl[T1] {
def apply[X]: T1[X,X] = implicitly[C[X] =:= C[X]]
}
def transform[A,B]: Eq[A,B] => C[A] =:= C[B] =
foldEq[A,B,T1](z1)
Existential Quantification
GADTs not only provide useful type equalities, they also offer existential quantification!
sealed abstract class Ex[F[_]] {
type hidden
val value: hidden
val evidence: F[hidden]
}
final case class MakeEx[F[_],A](value: A, evidence: F[A]) extends Ex[F] {
type hidden = A
}
Any value v:Ex[F]
has to be an instance of MakeEx[F,A]
for some type A
. Which means we have a value,
v.value
, of type A
and an instance of the type-class F
for A
(for example an instance of Monoid[A]
with F[X] = Monoid[X]
).
To transform values of type Ex[F]
into T
we need:
MakeEx[F[_],?]
being of type[A](A, F[A]) => Ex[F]
meaning:For_all_type A, (A, F[A]) => Ex[F]
, we need a functionf
of type[A](A, F[A]) => T
. Scala still does not support transparent higher ranked types, we need to emulate them with anothertrait
:
trait ElimMakeEx[F[_],T] {
def apply[A](value: A, evidence: F[A]): T
}
Then we can operate the transformation:
def foldEx[F[_], T](f: ElimMakeEx[F, T]): Ex[F] => T = {
def transform(v: Ex[F]): T =
v match {
case w@MakeEx(value, evidence) => f[w.hidden](value, evidence)
}
transform _
}
Duality
In this post we have deduced the fold
functions from the definition of each type. It is possible to
do the opposite: each constructor can be derived from the fold
function of its type. For example:
trait List[+A] {
def fold[T](z:T, f: (A,T) => T): T
}
def nil[A]: List[A] =
new List[A] {
def fold[T](z:T, f: (A,T) => T): T = z
}
def cons[A](head:A, tail: List[A]): List[A] =
new List[A] {
def fold[T](z:T, f: (A,T) => T): T = f(head, tail.fold(z,f))
}
def equality[A](l1: List[A], l2:List[A]): Boolean = ??? // Difficult but worthy exercice
Conclusion
I hope i convinced you folds are immensely useful. First, they let us write simply complex transform functions.
But this not the most interesting property. It is sometimes easier to define a type by its fold
function.
Java, for example, does not have support for neither sealed
classes nor pattern-matching. How could we define
the List
type so that Nil
and Cons
are the two only cases? The fold
function forces any instance of List
to fit into the desired shape (if some rules are obeyed like no null
and no runtime-reflection).
It can also happen that type-inference is not smart enough, fold
function provide an alternative way which is
often easier for the Scala
type-checker.