Functional Programming Glossary

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

Datatypes

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

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

Typeclasses

A typeclass is an interface representing one behavior associated with a type. Examples of this behavior are comparability (Eq), composability (Monoid), its contents can be mapped from one type to another (Functor), or error recovery (MonadError).

interface Eq<F>: Typeclass {
  fun eqv(a: F, b: F): Boolean
}

What differentiates typeclasses from regular interfaces is that they are meant to be implemented outside of their types. The association is done using generic parametrization rather than the usual subclassing. This means that they can be implemented for any class, even those not in the current project, and allows us to make typeclass instances available at a global scope for the single unique type they’re associated with.

Instances

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.

@instance
interface IntEqInstance: Eq<Int> {
  override fun eqv(a: Int, b: Int): Boolean = a == b
}

In Λrrow all typeclass instances can be looked up in a global scope using an inlined reified method with the same name as the typeclass. Its generic parameter will be used for the lookup, which reinforces the concept that most typeclasses should have a single implementation per type.

All the instances in the library are already registered and available in the global scope. If you’re defining your own instances and would like for them to be discoverable in the global scope you can add them by annotating them as @instance, and Λrrow’s annotation processor will register them for you.

import arrow.*
import arrow.typeclasses.*

eq<Int>()
//arrow.instances.IntEqInstance@1b82dc49

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, ListKW<A> or Option<A>. They’re called constructors because they’re similar to a factory function where the parameter is A, except for types. So, after applying the parameter Int to the type constructor ListKW<A> it returns a ListKW<Int>. This list isn’t parametrized in any generic value so it cannot be considered a type constructor anymore.

Like functions, a type constructor with several parameters like Either<L, R> can be partially applied for one of them to return another type constructor, for example Either<Throwable, A> or Either<E, String>.

Type constructors are useful when matched with typeclasses because they help us represent instances of parametrized classes that work for all generic parameters. As type constructors is not a first class feature in Kotlin we use an interface HK<F, A> to represent them. HK 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 HK<F, A>, if A is the type of the content then F has to be the type of the container. A malformed container would use the whole type constructor, duplicating the type HK<Option<A>, A>. What Λrrow does instead is define a surrogate type that’s not parametrized to represent F. These types are named same as the container and suffixed by HK, as in OptionHK or ListKWHK.

sealed class Option<A>: HK<OptionHK, A>

data class ListKW<A>(val list: List<A>): HK<ListKWHK, A>

You can read more about Higher Kinds and type constructors in KindedJ’s README. The library currently provides a layer of integration with KindedJ.

Using Higher Kinds with typeclasses

When HKs are coupled with typeclasses it allows us to define mapability using Functor for any content A inside a ListKW.

interface Functor<F>: Typeclass {
  fun <A, B> map(fa: HK<F, A>, f: (A) -> B): HK<F, B>
}

@instance
interface ListKWFunctorInstance : Functor<ListKWHK> {
  override fun <A, B> map(fa: HK<ListKWHK, A>, f: (A) -> B): ListKW<B> {
    val list: ListKW<A> = fa.ev()
    return list.map(f)
  }
}

You can see a function ev() used to access the map() function that already exists in ListKW. This is because we need to safely downcast from HK<ListKWHK, A> to ListKW<A>, and ev() is a global function defined to do so.

The function ev() is already defined for all datatypes in Λrrow. 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 simply by annotating it as @higerkind, and using Λrrow’s annotation processor will create them for you.

Note that the annotation @higerkind will also generate the integration typealiases required by KindedJ.

Using Higher Kinds and typeclasses with functions

Higher kinds can also be used to represent functions that are parametrized on type constructors. As long as you have a typeclass that can provide you with the behavior required to use such datatypes, you’re good to go!

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

interface Applicative<F>: Functor<F>, Typeclass {
  fun <A> pure(a: A): HK<F, A>
  
  /* ... */
}

object ListKWApplicativeInstance : ListKWFunctorInstance, Applicative<ListKWHK> {
  override fun <A> pure(a: A): HK<ListKWHK, A> = listOf(a)
  
  /* ... */
}

inline fun <reified F> randomUserStructure(f: (Int) -> User, AP: Applicative<F> = applicative<F>()) =
  AP.pure(f(Math.random()))

Remember that all instances already defined in Λrrow can be looked up globally

import arrow.data.*

applicative<ListKWHK>()
//arrow.data.ListKWApplicativeInstanceImplicits$instance$1@f24f973

And now this function randomUserStructure() can be used for any datatype that implements Applicative.

val list: ListKW<User> = randomUserStructure(::User).ev()
//[User(342)]

val option: Option<User> = randomUserStructure(::User).ev()
//Some(User(765))

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