-
Notifications
You must be signed in to change notification settings - Fork 0
Polymorphic Data Structures
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);
}
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");
}
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");
}
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");
}
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 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;
}
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;
}
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 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 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;
}
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;
}
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;
}
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;
}
}
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;
}
}
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;
}
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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);
}
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;
}
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
}
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
}
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
}
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);
}
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);
}
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);
}
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);
}
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);
}
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);
}
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);
}
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);
}
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);
}