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(head.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;
}

Remove Value 1

This function traverses a linked list and removes all occurrences of a value from a linked list. This is a polymorphic function that uses $T polymorphism.

remove_value :: (head: *Node($T), value: T) {
    if !head return;
    previous := head;
    current  := previous.next;
    while current {
        if current.data == value {
            previous.next = current.next;
        } else {
            previous = previous.next;
        }
        current = current.next;
    }
}

Remove Value 2

This function traverses a linked list and removes all occurrences of a value from a linked list. This is another version of the polymorphic function.

remove_value :: (head: *$T/Node, value: T.T) {
    if !head return;
    previous := head;
    current  := previous.next;
    while current {
        if current.data == value {
            previous.next = current.next;
        } else {
            previous = previous.next;
        }
        current = current.next;
    }
}

Remove Value 3

This function traverses a linked list and removes all occurrences of a value from a linked list. This is function that takes advantage of implicit polymorphism.

remove_value3 :: (head: *Node, value: head.T) {
    if !head return;
    previous := head;
    current  := previous.next;
    while current {
        if current.data == value {
            previous.next = current.next;
        } else {
            previous = previous.next;
        }
        current = current.next;
    }
}

Search 1

This is a polymorphic linked list search function where the Node has a polymorphic parameter $T.

search :: (head: *Node($T), value: T) -> *Node(T) {
    current := head;
    while current {
        if current.data == value {
            return current;
        }
        current = current.next;
    }
    return null;
}

Search 2

This is a polymorphic linked list search function where $T must be a parameterized struct of type Node.

search :: (head: *$T/Node, value: T.T) -> *T {
    current := head;
    while current {
        if current.data == value {
            return current;
        }
        current = current.next;
    }
    return null;
}

Search 3

This is a polymorphic linked list search function using implicit polymorphism.

search :: (head: *Node, value: head.T) -> type_of(head) {
    current := head;
    while current {
        if current.data == value {
            return current;
        }
        current = current.next;
    }
    return null;
}

Length 1

This is a polymorphic linked list length function where the Node has a polymorphic parameter $T.

length :: (head: *Node($T)) -> int {
    count := 0;
    current := head;
    while current {
        count += 1;
        current = current.next;
    }
    return count;
}

Length 2

This is a polymorphic linked list length function where $T must be a parameterized struct of type Node.

length :: (head: *$T/Node) -> int {
    count := 0;
    current := head;
    while current {
        count += 1;
        current = current.next;
    }
    return count;
}

Length 3

This is a polymorphic linked list length function using implicit polymorphism.

length :: (head: *Node) -> int {
    count := 0;
    current := head;
    while current {
        count += 1;
        current = current.next;
    }
    return count;
}

Reverse 1

This is a polymorphic linked list reverse function where the Node has a polymorphic parameter $T.

reverse1 :: (head: **Node($T)) {
    previous: *Node(T) = null;
    current := head.*;
    while current {
        next := current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    head.* = previous;
}

Reverse 2

This is a polymorphic linked list reverse function where $T must be a parameterized struct of type Node.

reverse :: (head: **$T/Node) {
    previous: *T = null;
    current := head.*;

    while current {
        next := current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    head.* = previous;
}

Reverse 3

This is a polymorphic linked list reverse function using implicit polymorphism.

reverse :: (head: **Node) {
    previous: type_of(head.*) = null;
    current := head.*;
    while current {
        next := current.next;
        current.next = previous;
        previous = current;
        current = next;
    }
    head.* = previous;
}

Tree

A binary tree is a hierarchical data structure where each node has at most two children: a left child and a right child. In Jai, we can implement this elegantly using structs and pointers.

Tree :: struct(T: Type) {
    data: T;
    left:  *Tree(T);
    right: *Tree(T);
}

Create Node

This function allocates a new tree node on the heap and initializes it with the given value.

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

Insert 1

This is a polymorphic tree insert function where the Node has a polymorphic parameter $T.

insert :: (root: **Tree($T), value: T) {
    // If tree is empty, create the root
    if !root.* {
        root.* = create_node(value);
        return;
    }

    // Recursively find the correct position
    if value < root.*.data {
        insert(*root.*.left, value);
    } else if value > root.*.data {
        insert(*root.*.right, value);
    }
    // If value equals data, we don't insert duplicates
}

Insert 2

This is a polymorphic insert function where $T must be a parameterized struct of type Tree.

insert :: (root: **$T/Tree, value: T.T) {
    // If tree is empty, create the root
    if !root.* {
        root.* = create_node(value);
        return;
    }

    // Recursively find the correct position
    if value < root.*.data {
        insert(*root.*.left, value);
    } else if value > root.*.data {
        insert(*root.*.right, value);
    }
    // If value equals data, we don't insert duplicates
}

Insert 3

This is a polymorphic insert function which uses implicit polymorphism.

insert :: (root: **Tree, value: type_of(root.*.data)) {
    // If tree is empty, create the root
    if !root.* {
        root.* = create_node(value);
        return;
    }

    // Recursively find the correct position
    if value < root.*.data {
        insert(*root.*.left, value);
    } else if value > root.*.data {
        insert(*root.*.right, value);
    }
    // If value equals data, we don't insert duplicates
}

Traverse Inorder 1

This is a polymorphic inorder tree traversal where the Tree has a polymorphic parameter $T.

traverse_inorder :: (root: *Tree($T)) {
    if !root return;
    traverse_inorder(root.left);
    print("% ", root.data);
    traverse_inorder(root.right);
}

Traverse Inorder 2

This is a polymorphic inorder tree traversal where $T must be a parameterized struct of type Tree.

traverse_inorder :: (root: *$T/Tree) {
    if !root return;
    traverse_inorder(root.left);
    print("% ", root.data);
    traverse_inorder(root.right);
}

Traverse Inorder 3

This is a polymorphic inorder tree traversal function which uses implicit polymorphism.

traverse_inorder :: (root: *Tree) {
    if !root return;
    traverse_inorder(root.left);
    print("% ", root.data);
    traverse_inorder(root.right);
}

Traverse Preorder 1

This is a polymorphic preorder tree traversal where the Tree has a polymorphic parameter $T.

traverse_preorder :: (root: *Tree($T)) {
    if !root return;
    print("% ", root.data);
    traverse_preorder(root.left);
    traverse_preorder(root.right);
}

Traverse Preorder 2

This is a polymorphic preorder tree traversal where $T must be a parameterized struct of type Tree.

traverse_preorder :: (root: *$T/Tree) {
    if !root return;
    print("% ", root.data);
    traverse_preorder(root.left);
    traverse_preorder(root.right);
}

Traverse Preorder 3

This is a polymorphic preorder tree traversal function which uses implicit polymorphism.

traverse_preorder :: (root: *Tree) {
    if !root return;
    print("% ", root.data);
    traverse_preorder(root.left);
    traverse_preorder(root.right);
}

Traverse Postorder 1

This is a polymorphic postorder tree traversal where the Tree has a polymorphic parameter $T.

traverse_postorder :: (root: *Tree($T)) {
    if !root return;
    traverse_postorder(root.left);
    traverse_postorder(root.right);
    print("% ", root.data);
}

Traverse Postorder 2

This is a polymorphic postorder tree traversal where $T must be a parameterized struct of type Tree.

traverse_postorder :: (root: *$T/Tree) {
    if !root return;
    traverse_postorder(root.left);
    traverse_postorder(root.right);
    print("% ", root.data);
}

Traverse Postorder 3

This is a polymorphic postorder tree traversal function which uses implicit polymorphism.

traverse_postorder :: (root: *Tree) {
    if !root return;
    traverse_postorder(root.left);
    traverse_postorder(root.right);
    print("% ", root.data);
}

Search 1

This is a polymorphic tree search where the Tree has a polymorphic parameter $T.

search :: (root: *Tree($T), value: T) -> *Tree(T) {
    // Base cases: empty tree or value found
    if !root || root.data == value {
        return root;
    }

    // Value is smaller, search left subtree
    if value < root.data {
        return search(root.left, value);
    }

    // Value is larger, search right subtree
    return search(root.right, value);
}

Search 2

This is a polymorphic tree search where $T must be a parameterized struct of type Tree.

search :: (root: *$T/Tree, value: T.T) -> *T {
    // Base cases: empty tree or value found
    if !root || root.data == value {
        return root;
    }

    // Value is smaller, search left subtree
    if value < root.data {
        return search(root.left, value);
    }

    // Value is larger, search right subtree
    return search(root.right, value);
}

Search 3

This is a polymorphic tree search function which uses implicit polymorphism.

search :: (root: *Tree, value: root.T) -> type_of(root) {
    // Base cases: empty tree or value found
    if !root || root.data == value {
        return root;
    }

    // Value is smaller, search left subtree
    if value < root.data {
        return search(root.left, value);
    }

    // Value is larger, search right subtree
    return search(root.right, value);
}

Find Minimum 1

This function finds the tree node with the smallest value of a binary search tree. This is a polymorphic function where the Tree has a polymorphic parameter $T.

find_minimum :: (root: *Tree($T)) -> *Tree(T) {
    if !root return null;
    // Keep going left until we can't anymore
    while root.left {
        root = root.left;
    }
    return root;
}

Find Minimum 2

This function finds the tree node with the smallest value of a binary search tree. This is a polymorphic tree search where $T must be a parameterized struct of type Tree.

find_minimum :: (root: *$T/Tree) -> *T {
    if !root return null;
    // Keep going left until we can't anymore
    while root.left {
        root = root.left;
    }
    return root;
}

Find Minimum 3

This function finds the tree node with the smallest value of a binary search tree. This is a polymorphic tree search that utilizes implicit polymorphism.

find_minimum :: (root: *Tree) -> type_of(root) {
    if !root return null;
    // Keep going left until we can't anymore
    while root.left {
        root = root.left;
    }
    return root;
}

Find Maximum 1

This function finds the tree node with the largest value of a binary search tree. This is a polymorphic function where the Tree has a polymorphic parameter $T.

find_maximum :: (root: *Tree($T)) -> *Tree(T) {
    if !root return null;
    // Keep going right until we can't anymore
    while root.right {
        root = root.right;
    }
    return root;
}

Find Maximum 2

This function finds the tree node with the largest value of a binary search tree. This is a polymorphic tree search where $T must be a parameterized struct of type Tree.

find_maximum :: (root: *$T/Tree) -> *T {
    if !root return null;
    // Keep going right until we can't anymore
    while root.right {
        root = root.right;
    }
    return root;
}

Find Maximum 3

This function finds the tree node with the largest value of a binary search tree. This is a polymorphic tree search that utilizes implicit polymorphism.

find_maximum :: (root: *Tree) -> type_of(root) {
    if !root return null;
    // Keep going right until we can't anymore
    while root.right {
        root = root.right;
    }
    return root;
}

Delete Node

Delete a node from the tree while maintaining the binary search tree correctness. This takes advantage of implicit polymorphism to generalize this function across all polymorphic Tree data structures.

delete :: (root: **Tree, value: type_of(root.*.data)) {
    if !root.* return;
    if value < root.*.data {
        delete(*root.*.left, value);
    } else if value > root.*.data {
        delete(*root.*.right, value);
    } else {
        node := root.*;
        // Case 1: No children (leaf node)
        if !node.left && !node.right {
            free(node);
            root.* = null;
        }
        // Case 2: Only right child
        else if !node.left {
            root.* = node.right;
            free(node);
        }
        // Case 2: Only left child
        else if !node.right {
            root.* = node.left;
            free(node);
        }
        // Case 3: Two children
        else {
            // Find the minimum value in right subtree (in-order successor)
            successor := find_minimum(node.right);

            // Copy the successor's value to this node
            node.data = successor.data;

            // Delete the successor
            delete(*node.right, successor.data);
        }
    }
}

Count Nodes 1

This function counts the number of nodes in a tree. This is a polymorphic function where the Tree has a polymorphic parameter $T.

count_nodes :: (root: *Tree($T)) -> int {
    if !root return 0;
    return 1 + count_nodes(root.left) + count_nodes(root.right);
}

Count Nodes 2

This function counts the number of nodes in a tree. This is a polymorphic function where $T must be a parameterized struct of type Tree.

count_nodes :: (root: *$T/Tree) -> int {
    if !root return 0;
    return 1 + count_nodes(root.left) + count_nodes(root.right);
}

Count Nodes 3

This function counts the number of node in a tree. This is a polymorphic tree search that utilizes implicit polymorphism.

count_nodes :: (root: *Tree) -> int {
    if !root return 0;
    return 1 + count_nodes(root.left) + count_nodes(root.right);
}

Height 1

This function computes the height of a tree. This is a polymorphic tree search that utilizes implicit polymorphism.

height :: (root: *Tree($T)) -> int {
    if !root return 0;
    left_height := height(root.left);
    right_height := height(root.right);
    return 1 + max(left_height, right_height);
}

Height 2

This function computes the height of a tree. This is a polymorphic function where $T must be a parameterized struct of type Tree.

height :: (root: *$T/Tree) -> int {
    if !root return 0;
    left_height := height(root.left);
    right_height := height(root.right);
    return 1 + max(left_height, right_height);
}

Height 3

This function computes the height of a tree. This is a polymorphic tree search that utilizes implicit polymorphism.

height :: (root: *Tree) -> int {
    if !root return 0;
    left_height := height(root.left);
    right_height := height(root.right);
    return 1 + max(left_height, right_height);
}