Linked List using ADTs

Let's see how we can make use of Ryna's features to program a Linked List. This will guide you through all the design process and all the common pitfalls that you might face.

What is a Linked List?

A Linked List is a common data structure that is used to store several elements in sequence. It's not the same as an array, since those store elements sequentially in memory and Linked Lists do not. This makes these structures useful for very big, constantly growing data.

A Linked List consists of a series of nodes with references to the next node in the sequence. Every node has an element of the list except for theh last one, that is called sentinel and just marks the end of the list:

%% mermaid
graph LR
    1 --> 2
    2 --> 3
    3 --> ...
    ... --> End

A first approach

These are probably the most common recursive data structure to implement when learning about algebraic data types. The basic idea is to first create an empty class for the sentinel (usually called Nil):

class Nil {}

After this, you can represent a Linked List (of Ints, for example) like this:

type List = Nil | (Int, List);

This means that a Linked List is either an empty List (Nil) or a value followed by another List. This recursion is enough to make it store any amount of data:

let a: List = Nil();            // Empty list
let b: List = (1, Nil());       // List of one element
let c: List = (2, (1, Nil()));  // List of two elements
[...]

After this, you can build some utility functions:

// Add a new element
fn add(list: List, number: Int) -> List {
    return (*number, *list);
}

// Get every element but the first
fn rest(list: @List) -> @List {
    return list.as<@(Int, List)>().get_1();
}

// Get size of the list
fn size(list: @List) -> Int {
    if list.is<@Nil>() { // The size of an empty list is 0
        return 0;
    }

    return 1 + list.rest().size(); // Else the size is 1 + the size of the rest
}

Note that these functions are not crafted to avoid unnecessary copies, so they might be made more efficient.

Going generic

Now you might want to make the structure generic, this is actually not very difficult given what we have:

type List<T> = Nil | ('T, List<'T>);

Now this code is legal:

let a: List<Int> = Nil();                  // Empty list
let b: List<Bool> = (true, Nil());         // List of one element
let c: List<Float> = (2.2, (1.1, Nil()));  // List of two elements
[...]

Adapting the rest of the functions is left as an exercise to the reader :)