Search

Functional Programming Glossary

Note: This section keeps on growing! Keep an eye on it from time to time.

This document is meant to be an introduction to Functional Programming for people from all backgrounds. We’ll go through some of the key concepts, and then dive into their implementation in real world cases.

Some similar documents focused on explaining general concepts, rather than Arrow’s versions, can be found for examples in JavaScript and in Scala.

Datatypes

A datatype is a class that encapsulates one reusable coding pattern. These solutions have a canonical implementation that is generalized for all possible uses.

Some common patterns expressed as datatypes are absence handling with Option, branching in code with Either, or interacting with the platform the program runs in using suspend.

Some of these patterns are implemented using a mix of sealed classes, where each inheritor is a data class. For example, the internal representation of an Option is a sealed class with two data classes: Some<A>(val a: A), and None. And Ior is a sealed class with three data class inheritors: Left(val a: A), Right(val b: B), and Both(val a: A, val b: B).

Typeclasses

Typeclasses are interface abstractions that define a set of extension functions associated to one type. These extension functions are canonical and consistent across languages and libraries. And they have inherent mathematical properties that are testable, such as commutativity or associativity.

Examples of behaviors abstracted by typeclasses are: Comparability (Eq), composability (Monoid), its contents can be mapped from one type to another (Functor), or error recovery (MonadError).

Typeclasses have two main uses:

  • Add new functionality to types. For example, if I know how to compare two objects, I can add a new extension function to check for inequality. Or, if I know how to aggregate objects together, I can add an extension function for List that aggregates all of its elements. The number of extra extension functions that you get per typeclass can be from one in Eq to 17 (!) in Foldable.

  • Abstracting over behavior. Like any other interface, you can use them in your functions and classes as a way of talking about the capabilities of the implementation, without exposing the details. This way, you can create APIs that work the same for Option or Observable.

You can read more about all the typeclasses that Arrow provides in its section of the docs.

Let’s dive into one example. The typeclass Eq parametrized to F defines equality between two objects of type F:

interface Eq<F> {
  fun F.eqv(b: F): Boolean

  fun F.neqv(b: F): Boolean =
    !eqv(b)
}

Instances and Extensions Interfaces

A single implementation of a typeclass for a specific datatype or class. Because typeclasses require generic parameters, each implementation is meant to be unique for that parameter.

For example, given a class like this:

data class User(val id: Int) {
  companion object
}

We can declare that instances of this class can be equated based on their id property, and, therefore, that User itself is an instance of the Eq typeclass:

import arrow.extension

@extension
interface UserEq: Eq<User> {
  override fun User.eqv(b: User): Boolean = id == b.id
}

Note that classes must have companion objects for this to work. All typeclass instances provided by Arrow can be found in the companion object of the type they’re defined for, including platform types like String or Int.

import arrow.*
import arrow.core.*
import arrow.core.extensions.*
import arrow.typeclasses.*
import arrow.core.extensions.option.functor.*
import arrow.core.extensions.either.monadError.*
import arrow.core.extensions.listk.traverse.*

String.eq()

Option.functor()

import arrow.core.extensions.mapk.semigroup.*

MapK.semigroup<String, Int>(Int.semigroup())

Either.monadError<Throwable>()

ListK.traverse()

If you’re defining your own instances and would like for them to be discoverable in their corresponding datatypes’ companion object, you can generate it by annotating them as @extension, and Arrow’s annotation processor will create the extension functions for you.

NOTE: If you’d like to use @extension for transitive typeclasses, like a Show<List<A>> that requires a function returning a Show<A>, you’ll need the function providing the transitive typeclass to have 0 parameters. This will make the transitive typeclass a parameter of the extension function.

Syntax

When creating an instance with the @extension annotation, the processor generates extension functions for the types that are available simply by importing them. See, for example, the coroutine function binding, the constructor map, and the method sequence defined in the instances of Monad, Applicative, and Traverse:

import arrow.core.Option
import arrow.core.computations.option

option.eager<Int> {
  val a = Option(1).bind()
  val b = Option(a + 1).bind()
  a + b
}

import arrow.core.Option

Option(1).zip(Option(2), Option(3)) { one, two, three ->
  one + two + three
}
// Option.Some(6)

import arrow.core.extensions.list.traverse.sequence
import arrow.core.extensions.option.applicative.applicative

listOf(Option(1), Option(2), Option(3)).sequence(Option.applicative())

import arrow.core.Some
import arrow.core.computations.option

option.eager<Int> {
    val a = Some(1).bind()
    val b = Some(a+1).bind()
    a + b
}
// Option.Some(3)

import arrow.core.Option

Some(1).zip(Some(2), Some(3)) { one, two, three ->
  one + two + three
}

import arrow.core.Right
import arrow.core.sequenceEither

listOf(Right(1), Right(2), Right(3)).sequenceEither()

Type constructors

NOTE: This approach to type constructors will be simplified if KEEP-87 is approved. Go vote!

A type constructor is any class or interface that has at least one generic parameter. For example, ListK<A> or Option<A>. They’re called constructors because they’re similar to a factory function where the parameter is A, except type constructors only work for types. So, we could say that, after applying the parameter Int to the type constructor ListK<A>, it returns a ListK<Int>. As ListK<Int> isn’t parametrized in any generic value, it is not considered a type constructor anymore, just a regular type.

As with functions, a type constructor with several parameters like Either<L, R> can be partially applied for one of them to return another type constructor with one fewer parameter. For example, applying Throwable to the left side yields Either<Throwable, A>, or applying String to the right side results in Either<E, String>.

Type constructors are useful when matched with typeclasses because they help us represent instances of parametrized classes — the containers — that work for all generic parameters — the content. As type constructors is not a first class feature in Kotlin, Λrrow uses an interface Kind<F, A> to represent them. Kind stands for Higher Kind, which is the name of the language feature that allows working directly with type constructors.

Higher Kinds

In a Higher Kind with the shape Kind<F, A>, if A is the type of the content, then F has to be the type of the container.

A malformed Higher Kind would use the whole type constructor to define the container, duplicating the type of the content Kind<Option<A>, A>. This incorrect representation has a large number of issues when working with partially applied types and nested types.

What Λrrow does instead is define a surrogate type that’s not parametrized to represent F. These types are named the same as the container and prefixed by For-, as in ForOption or ForListK. You have seen these types used in the Syntax section above!

class ForOption private constructor() { companion object {} }

sealed class Option<A>: Kind<ForOption, A>

class ForListK private constructor() { companion object {} }

data class ListK<A>(val list: List<A>): Kind<ForListK, A>

As ListK<A> is the only existing implementation of Kind<ForListK, A>, we can define an extension function on Kind<ForListK, A> to do the downcasting safely for us. This function by convention is called fix(), as in fixing a type from something generic into something concrete.

fun <A> Kind<ForListK, A>.fix() = this as ListK<A>

This way, we can convert from ListK<A> to Kind<ForListK, A> via simple subclassing, and from Kind<ForListK, A> to ListK<A> using the function fix(). Being able to define extension functions that work for partially applied generics is a feature from Kotlin that’s not available in Java. You can define fun Kind<ForOption, A>.fix() and fun Kind<ForListK, A>.fix(), and the compiler can smartly decide which one you’re trying to use. If it can’t, it means there’s an ambiguity you should fix!

The function fix() is already defined for all datatypes in Λrrow, alongside a typealias for its Kind<F, A> specialization done by suffixing the type with Of, as in ListKOf<A> or OptionOf<A>. If you’re creating your own datatype that’s also a type constructor and would like to create all these helper types and functions, you can do so by simply annotating it as @higherkind, and the Λrrow’s annotation processor will create them for you.

@higherkind data class ListK<A>(val list: List<A>): ListKOf<A>

// Generates the following code:
//
// class ForListK private constructor() { companion object {} }
// typealias ListKOf<A> = Kind<ForListK, A>
// fun ListKOf<A>.fix() = this as ListK<A>

Note that the annotation @higherkind will also generate the integration typealiases required by KindedJ as long as the datatype is invariant. You can read more about sharing Higher Kinds and type constructors across JVM libraries in KindedJ’s README.

Using Higher Kinds with typeclasses

Now that we have a way of representing generic constructors for any type, we can write typeclasses that are parametrised for containers.

Let’s use as an example a typeclass that specifies how to map the contents of any container F. This typeclass that comes from computer science is called a Functor.

interface Functor<F> {
  fun <A, B> Kind<F, A>.map(f: (A) -> B): Kind<F, B>
}

See how the class is parametrized on the container F, and the function is parametrized to the content A. This way, we can have a single representation that works for all mappings from A to B.

Let’s define an instance of Functor for the datatype ListK, our own wrapper for lists.

@extension
interface ListKFunctor : Functor<ForListK> {
  override fun <A, B> Kind<ForListK, A>.map(f: (A) -> B): Kind<ForListK, B> {
    return this.fix().map(f)
  }
}

This interface extends Functor for the value F of ListK. We use an annotation processor @extension to generate an object out of an interface with all the default methods already defined, and to add an extension function to get it into the companion object of the datatype. The @extension processor also projects all type class declared functions into the data type that it’s extending as extensions functions. These extensions functions may be imported a la carte when working with concrete data types.

@extension
interface ListKFunctor : Functor<ForListK>

// Somewhere else in the codebase
ListK.functor()

The signature of map takes a parameter Kind<ForListK, A>, which is the receiver and a mapping function from A to B, once the types have been replaced. This means that map will work for all instances of ListK<A> for whatever the value of A can be.

override fun <A, B> Kind<ForListK, A>.map(f: (A) -> B): ListK<B>

The implementation is short. On the first line, we downcast Kind<ForListK, A> to ListK<A> using fix(). Once the value has been downcasted, the implementation of map inside the ListK<A> we have obtained already implements the expected behavior of map.

val list: ListK<A> = this.fix()
return list.map(f)

Using Higher Kinds and typeclasses with functions

Higher kinds are also used to model functions that require a datatype to implement a typeclass. This way, you can create functions that abstract behavior (defined by a typeclass) and allow callers to define which datatype they’d like to apply it to.

Let’s use the typeclass Applicative that contains the constructor function just().

interface Applicative<F>: Functor<F> {

  // Constructs the current datatype with a value of type A inside
  fun <A> just(a: A): Kind<F, A>

}

Once we have this typeclass behavior defined, we can now write a function that’s parametrized for any F that has one instance of Applicative. The function uses the constructor just to create a value of type Kind<F, User>, effectively generifying the return on any container F.

fun <F> Applicative<F>.randomUserStructure(f: (Int) -> User): Kind<F, User> =
  this.just(f(Math.random().toInt()))

Now let’s create a simple example instance of Applicative, where our F is ListK. This implementation of a just constructor is trivial for lists, as it just requires wrapping the value.

@extension
interface ListKApplicative : Applicative<ForListK> {
  override fun <A> just(a: A): Kind<ForListK, A> = ListK(listOf(a))
}

And now we can show how this function randomUserStructure() can be used for any datatype that implements Applicative. As the function returns a value Kind<F, User>, the caller is responsible for calling fix() to downcast it to the expected value.

val list = ListK.applicative().randomUserStructure(::User).fix()
//[User(342)]

val option = Option.applicative().randomUserStructure(::User).fix()
//Some(User(765))

val either = Either.applicative<Unit>().randomUserStructure(::User).fix()
//Right(User(221))

Passing the instance in every function call seems like a burden. So, because randomUserStructure is an extension function for Applicative, we can omit the implicit parameter as long as we are within the scope of an Applicative instance. You can use the standard functions with and run for this.

with (ListK.applicative()) {
    // Lots of Kotlin here

    // Multiple calls

    randomUserStructure(::User).fix()
}
// [User(342)]

Option.applicative().run {
    tupled(randomUserStructure(::User), randomUserStructure(::User))
}
// Some(value = Tuple2(a = User(765), b = User(127)))

It is also possible to use a form of Dependency Injection to make the typeclass scope available to a whole class. For example, using simple delegation:

class UserFetcher<F>(AP: Applicative<F>): Applicative<F> by AP {
    fun genUser() = randomUserStructure(::User)
}

UserFetcher(Option.applicative()).genUser().fix()
// Some(value = User(943))

To learn more about this Typeclassless technique, you should head to the Dependency Injection documentation.

Side-effects and Effects

A side-effect is a statement that changes something in the running environment. Generally, this means setting a variable, displaying a value on screen, writing to a file or a database, logging, start a new thread . . .

When talking about side-effects, we generally see functions that have the signature (...) -> Unit, meaning that, unless the function doesn’t do anything, there’s at least one side-effect. Side-effects can also happen in the middle of another function, which is an undesirable behavior in Functional Programming.

Side-effects are too general to be unit tested for because they depend on the environment. They also have poor composability. Overall, they’re considered to be outside the Functional Programming paradigm, and are often referred to as “impure” functions.

Because side-effects are unavoidable in any program, FP provides several datatypes for dealing with them! One way is by abstracting their behavior. The simplest examples of this are the Writerdatatype, which allows you to write to an information sink like a log or a file buffer; or State datatype, which simulates scoped mutable state for the duration of an operation.

For more complicated effects that can throw or jump threads, we need more advanced techniques. We model side-effects in kotlin with suspend functions and Kotlin Continuations. These continuations compose, catch exceptions, control asynchrony, and, most importantly, can be run lazily. This gets rid of the issues with side-effects.

Although one can also write the whole program in an imperative way inside a single Effect wrapper, that wouldn’t be very efficient, as you don’t get any of its benefits. :D

Do you like Arrow?

✖
Arrow Org
<
Join us at
>
slack.kotlinlang.org #arrow