Generics and Type Level Abstractions

Generic Algebraic Data Types

So far we’ve only taken a look at ADTs based on concrete types. However, one might notice that dealing with concrete types can become cumbersome.

Consider, for instance, the very common Option type. Implementing it with only concrete types would require defining a new type for each type that needs to be wrapped in an Option.

type OptionInt {
  Some(Int)
  None
}

type OptionFloat {
  Some(Float)
  None
}

// ...

Basic functionality for OptionInt and OptionFloat such as is_some and map would share the same code, so it makes sense to define these functions more generally.

Luckily, Gleam, as well as many other programming languages, provides a construction for declaring types and functions in a way that they accept any type of input.

This construction is generally referred to as generics and it allows the programmer to instruct the compiler to automatically generate code for different types and requires less typing from us programmers.

pub type Option(a) {
    Some(a)
    None
}

Take a look at the generic implementation of Option in the listing above. The type constructor Option accepts a type as an argument and returns a type, meaning it’s like a function between types.

Using the generic Option in type signature, requires passing it the type parameter a, which can be a concrete type such as Int or another generic one.

fn to_option(n: Int) -> Option(Int) {
    Some(n)
}

fn map(self: Option(a), f: fn(a) -> b) -> Option(b) {
    case self {
        Some(val) -> Some(f(val))
        None -> None
    }
}

As mentioned, a type can also be generic over multiple other types. For example, a generic implementation of Result would look like this:

pub type Result(a, b) {
    Ok(a)
    Error(b)
}

A generic List

In the previous chapter, we implemented various methods for a List consisting of Ints. Now, we are ready to take that to the next level with the help of generics.

pub type List(a) {
    Cons(a, List(a))
    Nil
}

With the generic definition of a List, we’re ready to tackle implementing generic methods for it. In these methods, pay close attention to the type signature of the functions.

Starting off with the simple ones, below is a generic implementation of head that returns an Option(a).

// Import Option type and data constructors
// from the Gleam standard library
import gleam/option.{type Option, Some, None}

pub fn head(l: List(a)) -> Option(a) {
    case l {
        Cons(h, _) -> Some(h)
        Nil -> None
    }
}

We can write the type signature of head as

In the previous chapter we had a map function for integer lists.

Reminder: The map function had this function declaration:

fn map(f: fn(Int) -> Int, l: List) -> List

The map function can also be implemented for a generic List. In this case, the function applied doesn’t necessarily have to output the same type it takes in, and therefore it’s type signature is a -> b. Based on this, the type of the generic map function is

This means that the map function takes in arguments of type and and returns a . The implementation is identical to what we had in the previous chapter, except that we are actually working with generic types rather than integers:

pub fn map(f: fn(a) -> b, l: List(a)) -> List(b) {
    case l {
        Cons(h, t) -> Cons(f(h), map(f, t))
        Nil -> Nil
    }
}

case l {
    Cons(h, t) -> Cons(id(h), map(id, t))
    Nil -> Nil
}

case l {
    Cons(h, t) -> Cons(h, t)
    Nil -> Nil
}

Folding

Now that we’ve learned about generics, we can introduce ourselves to another important List processing function. Let’s do this by implementing a more generic version of the sum function introduced in the previous chapter. The function is called fold. Fold “folds” a list to a single value using a function of type fn(b, a) -> b.

The value of type b, which is eventually returned is commonly referred to as the “accumulator”, because it is accumulated throughout the list. Implementations of fold require the user to specify a starting value for acc.

fn fold(acc: b, f: fn(b, a) -> b, l: List(a)) -> b {
    case l {
        Cons(h, t) -> fold(f(acc, h), f, t)
        Nil -> acc
    }
}

// sum() is a special case of fold
fn sum(l: List(Int)) -> Int {
    fold(0, fn(a, b) { a + b }, l)
}

In addition to the sum function, fold can be used to implement many of the common List processing functions. For example, let’s try implementing the filter function using fold.

fn filter(pred: fn(a) -> Bool, l: List(a)) -> List(a) {
    fold(Nil, fn(acc, e) {
        case pred(e) {
            True -> Cons(e, acc)
            False -> acc
        }
    }, l)
}

import gleam/io
pub fn main() {
    let list = Cons(1, Cons(2, Cons(3, Cons(4, Nil))))
    io.debug(filter(fn(a) { a % 2 == 0 }, list))
    // -> Cons(4, Cons(2, Nil))
}

Our attempt seems to work correctly, except for the fact that it produces the result in reverse order. This makes sense if we think about it, the acc starts as an empty list, and then if an element matches the predicate, we add it to the front of the acc therefore producing the result in reverse order.

For this very reason, there often exist two variants of the fold function, fold_left and fold_right (sometimes abbreviated to foldl and foldr respectively). The fold function we have implemented is a left-fold, because it starts folding from the left side of the list. A right-fold would look like this instead:

pub fn foldr(acc: b, f: fn(b, a) -> b, l: List(a)) -> b {
  case l {
    Cons(h, t) -> f(foldr(acc, f, t), h)
    Nil -> acc
  }
}

Now if we substitute the fold in our filter implementation with the foldr we get the desired results.

Footnotes