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;
}