Polymorphic Data Structures

Polymorphic Linked List

A polymorphic linked list can be defined by using a parenthesized struct with type parameters T: Type. To specify a different linked list type, just change the T: Type parameter to match what one desires. This approach allows one to create linked lists of integers, floats, strings, etc. and generalize the linked list data structure across all different types.

Node :: struct(T: Type) {
    data: T;
    next: *Node(T);
}

Print Linked List 1

Given Linked List definition above, one can write a polymorphic print linked list function and specific $T parameter to allow the type of the function to be determined at compile time.

print_linked_list :: (node: *Node($T)) {
    print("[");
    while node {
        print("%, ", node.data);
        node = node.next;
    }
    print("]\n");
}

Print Linked List 2

This is another polymorphic print linked list, but instead of parameterizing the Node parameter the $T, one parameterizes the entire struct. This has the same functionality of the previous print, but slightly different error messages.

print_linked_list :: (node: *$T/Node) {
    print("[");
    while node {
        print("%, ", node.data);
        node = node.next;
    }
    print("]\n");
}

Print Linked List 3

This is a implicit polymorphism version of the print linked list function. This functions exactly the same as previous functions, except the polymorphism is implicit rather than explicit. Implicit polymorphism allows easy conversion of functions manipulating data structures into polymorphic functions, reducing friction when refactoring code into more polymorphic code.

print_linked_list :: (node: *Node) {
    print("[");
    while node {
        print("%, ", node.data);
        node = node.next;
    }
    print("]\n");
}

Instantiating a node

This function instantiates a polymorphic linked list node. This function generalizes across all different types of nodes.

create_node :: (value: $T) -> *Node(T) {
    node := New(Node(T));
    node.data = value;
    node.next = null;
    return node;
}

Append Front 1

Append front can be transformed into a polymorphic function in the following way.

append_front :: (head: **Node($T), data: T) {
    new_node := New(Node(T));
    new_node.data = data;
    new_node.next = head.*;
    head.* = new_node;
}

Append Front 2

One can switch around the $T to the second parameter if one wants to.

append_front :: (head: **Node(T), data: $T) {
    new_node := New(Node(T));
    new_node.data = data;
    new_node.next = head.*;
    head.* = new_node;
}

Append Front 3

This is another way of writing a polymorphic append front.

append_front :: (head: **$T/Node, data: T.T) {
    new_node := New(Node(T.T));
    new_node.data = data;
    new_node.next = head.*;
    head.* = new_node;
}

Append 1

Append can be made into a polymorphic function using the following method.

// create a node at the end of the list.
append :: (head: *Node($T), data: T) {
    assert(head != null);
    // initialize new node to append.
    new_node := New(Node(T));
    new_node.data = data;
    new_node.next = null;

    // traverse to the end of linked list.
    while(head.next) {
        head = head.next;
    }

    // append to the end of linked list.
    head.next = new_node;
}

Append 2

Append can be made into a polymorphic function using the following method.

// create a node at the end of the list.
append :: (head: *Node, data: head.T) {
    assert(head != null);
    // initialize new node to append.
    new_node := New(Node(T));
    new_node.data = data;
    new_node.next = null;

    // traverse to the end of linked list.
    while(head.next) {
        head = head.next;
    }

    // append to the end of linked list.
    head.next = new_node;
}

Insert Sorted 1

This function inserts an element into a sorted linked list. This polymorphic function applies the $T on the Node parameterized struct.

insert_sorted :: (head: **Node($T), value: T) {
    new_node := create_node(value);

    // Empty list or insert at beginning
    if !head.* || head.*.data >= value {
        new_node.next = head.*;
        head.* = new_node;
        return;
    }

    // Find insertion point
    current := head.*;
    while current.next && current.next.data < value {
        current = current.next;
    }

    // Insert after current
    new_node.next = current.next;
    current.next = new_node;
}

Insert Sorted 2

This is another function that inserts an element into a sorted linked list.

insert_sorted2 :: (head: **$T/Node, value: T.T) {
    new_node := create_node(value);

    // Empty list or insert at beginning
    if !head.* || head.*.data >= value {
        new_node.next = head.*;
        head.* = new_node;
        return;
    }

    // Find insertion point
    current := head.*;
    while current.next && current.next.data < value {
        current = current.next;
    }

    // Insert after current
    new_node.next = current.next;
    current.next = new_node;
}