o
langpkg/odin
packages/library/list
l

list

v8727f00library

No description provided.

0 stars1 forksUnknownupdated 11 months ago
Open repo

Functional List Library for Odin

A functional, immutable linked list implementation for the Odin programming language. This library provides a complete set of operations for working with linked lists in a functional programming style.

Features

  • Immutable: All operations return new lists, original lists are never modified
  • Generic: Works with any type using Odin's generic system
  • Memory Safe: Proper memory management with explicit cleanup
  • Functional: Supports higher-order functions like map, filter, and fold
  • Complete API: Full set of list operations including creation, manipulation, and traversal

Table of Contents

Installation

Simply include the list.odin file in your project and import the package:

import "path/to/list"

Quick Start

package main

import "core:fmt"
import "path/to/list"

main :: proc() {
    // Create a list from an array
    my_list := list.from_array([]int{1, 2, 3, 4, 5})

    // Print the list
    list.print(my_list)  // Output: [1, 2, 3, 4, 5]

    // Add elements to the front
    new_list := list.cons(my_list, 0)
    list.print(new_list)  // Output: [0, 1, 2, 3, 4, 5]

    // Map over the list
    double := proc(x: int) -> int { return x * 2 }
    doubled := list.map_list(my_list, double)
    list.print(doubled)  // Output: [2, 4, 6, 8, 10]

    // Clean up memory
    list.destroy(my_list)
    list.destroy(new_list)
    list.destroy(doubled)
}

API Reference

Creation and Initialization

init(el: $T, allocator := context.allocator) -> ^List(T)

Creates a new list with a single element.

list1 := list.init(42)
// Creates: [42]

from_array(arr: []$T, allocator := context.allocator) -> ^List(T)

Creates a list from an array, preserving order.

numbers := []int{1, 2, 3, 4, 5}
my_list := list.from_array(numbers)
// Creates: [1, 2, 3, 4, 5]

Basic Operations

cons(l: ^List($T), el: T, allocator := context.allocator) -> ^List(T)

Adds an element to the front of a list (supports single elements, arrays, or other lists).

// Single element
list1 := list.cons(my_list, 0)
// Array
list2 := list.cons(my_list, []int{-2, -1})
// Another list
list3 := list.cons(list1, list2)

head(l: ^List($T)) -> T

Returns the first element of the list.

first := list.head(my_list)  // Returns first element

tail(l: ^List($T)) -> ^List(T)

Returns a new list with all elements except the first.

rest := list.tail(my_list)  // Returns list without first element

is_empty(l: ^List($T)) -> bool

Checks if a list is empty (nil).

empty := list.is_empty(nil)        // true
not_empty := list.is_empty(my_list) // false

length(l: ^List($T)) -> int

Returns the number of elements in the list.

len := list.length(my_list)  // Returns count of elements

member(el: $T, l: ^List(T)) -> bool

Checks if an element exists in the list.

exists := list.member(3, my_list)     // true if 3 is in the list
missing := list.member(99, my_list)   // false if 99 is not in the list

at(l: ^List($T), index: int) -> (T, bool)

Gets the element at a specific index (0-based).

if value, ok := list.at(my_list, 2); ok {
    fmt.printf("Element at index 2: %d\n", value)
}

List Manipulation

append_list(l: ^List($T), el: T, allocator := context.allocator) -> ^List(T)

Adds an element to the end of the list.

appended := list.append_list(my_list, 999)
// Adds 999 to the end

reverse(l: ^List($T), allocator := context.allocator) -> ^List(T)

Returns a new list with elements in reverse order.

reversed := list.reverse(my_list)
// [1,2,3,4,5] becomes [5,4,3,2,1]

take(l: ^List($T), n: int, allocator := context.allocator) -> ^List(T)

Returns a new list with the first n elements.

first_three := list.take(my_list, 3)
// Takes first 3 elements

drop(l: ^List($T), n: int, allocator := context.allocator) -> ^List(T)

Returns a new list without the first n elements.

without_first_two := list.drop(my_list, 2)
// Drops first 2 elements

copy_list(l: ^List($T), allocator := context.allocator) -> ^List(T)

Creates a deep copy of the list.

copy := list.copy_list(my_list)
// Independent copy of the list

Higher-Order Functions

map_list(l: ^List($T), f: proc(_: T) -> $U, allocator := context.allocator) -> ^List(U)

Applies a function to each element, returning a new list.

double := proc(x: int) -> int { return x * 2 }
doubled := list.map_list(my_list, double)
// [1,2,3] becomes [2,4,6]

// Type transformation
to_string := proc(x: int) -> string { return fmt.aprintf("%d", x) }
strings := list.map_list(my_list, to_string)
// [1,2,3] becomes ["1","2","3"]

filter(l: ^List($T), pred: proc(_: T) -> bool, allocator := context.allocator) -> ^List(T)

Returns a new list containing only elements that satisfy the predicate.

is_even := proc(x: int) -> bool { return x % 2 == 0 }
evens := list.filter(my_list, is_even)
// [1,2,3,4,5] becomes [2,4]

is_positive := proc(x: int) -> bool { return x > 0 }
positives := list.filter(my_list, is_positive)

foldl(l: ^List($T), init: $U, f: proc(_: U, _: T) -> U) -> U

Folds the list from the left (tail recursive).

sum := proc(acc: int, x: int) -> int { return acc + x }
total := list.foldl(my_list, 0, sum)
// Calculates sum of all elements

concat := proc(acc: string, x: string) -> string { return acc + x }
result := list.foldl(string_list, "", concat)
// Concatenates all strings

foldr(l: ^List($T), init: $U, f: proc(_: T, _: U) -> U) -> U

Folds the list from the right.

cons_func := proc(x: int, acc: ^List(int)) -> ^List(int) {
    return list.cons(acc, x)
}
copy := list.foldr(my_list, nil, cons_func)
// Creates a copy using foldr

Conversion Functions

to_array(l: ^List($T), allocator := context.allocator) -> []T

Converts a list to an array.

arr := list.to_array(my_list)
// Returns: []int{1, 2, 3, 4, 5}

Utility Functions

print(l: ^List($T))

Prints the list in a readable format.

list.print(my_list)
// Output: [1, 2, 3, 4, 5]

destroy(l: ^List($T))

Frees all memory allocated for the list.

list.destroy(my_list)  // Always call this when done with a list

Usage Examples

Basic List Operations

package main

import "core:fmt"
import "path/to/list"

main :: proc() {
    // Create lists
    list1 := list.init(10)
    list2 := list.from_array([]int{1, 2, 3, 4, 5})

    fmt.println("=== Basic Operations ===")

    // Print lists
    fmt.print("List 1: "); list.print(list1)
    fmt.print("List 2: "); list.print(list2)

    // Check properties
    fmt.printf("Length of list2: %d\n", list.length(list2))
    fmt.printf("Head of list2: %d\n", list.head(list2))
    fmt.printf("Is 3 a member: %t\n", list.member(3, list2))

    // Access elements
    if val, ok := list.at(list2, 2); ok {
        fmt.printf("Element at index 2: %d\n", val)
    }

    // Cleanup
    list.destroy(list1)
    list.destroy(list2)
}

Functional Programming Patterns

package main

import "core:fmt"
import "path/to/list"

main :: proc() {
    numbers := list.from_array([]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10})

    fmt.println("=== Functional Programming ===")

    // Chain operations: filter evens, double them, take first 3
    is_even := proc(x: int) -> bool { return x % 2 == 0 }
    double := proc(x: int) -> int { return x * 2 }

    evens := list.filter(numbers, is_even)
    fmt.print("Even numbers: "); list.print(evens)

    doubled_evens := list.map_list(evens, double)
    fmt.print("Doubled evens: "); list.print(doubled_evens)

    first_three := list.take(doubled_evens, 3)
    fmt.print("First 3: "); list.print(first_three)

    // Fold operations
    sum_func := proc(acc: int, x: int) -> int { return acc + x }
    total := list.foldl(numbers, 0, sum_func)
    fmt.printf("Sum of all numbers: %d\n", total)

    // Cleanup
    list.destroy(numbers)
    list.destroy(evens)
    list.destroy(doubled_evens)
    list.destroy(first_three)
}

Working with Different Types

package main

import "core:fmt"
import "path/to/list"

main :: proc() {
    fmt.println("=== Different Types ===")

    // String list
    words := list.from_array([]string{"hello", "functional", "world"})
    fmt.print("Words: "); list.print(words)

    // Boolean list
    flags := list.from_array([]bool{true, false, true, false})
    fmt.print("Flags: "); list.print(flags)

    // Float list
    floats := list.from_array([]f32{3.14, 2.71, 1.41, 1.73})
    fmt.print("Floats: "); list.print(floats)

    // Type transformation with map
    length_func := proc(s: string) -> int { return len(s) }
    lengths := list.map_list(words, length_func)
    fmt.print("Word lengths: "); list.print(lengths)

    // Cleanup
    list.destroy(words)
    list.destroy(flags)
    list.destroy(floats)
    list.destroy(lengths)
}

List Manipulation

package main

import "core:fmt"
import "path/to/list"

main :: proc() {
    fmt.println("=== List Manipulation ===")

    // Create two lists
    list_a := list.from_array([]int{1, 2, 3})
    list_b := list.from_array([]int{4, 5, 6})

    fmt.print("List A: "); list.print(list_a)
    fmt.print("List B: "); list.print(list_b)

    // Concatenate lists
    combined := list.cons(list_a, list_b)
    fmt.print("Combined: "); list.print(combined)

    // Reverse
    reversed := list.reverse(combined)
    fmt.print("Reversed: "); list.print(reversed)

    // Append to end
    with_zero := list.append_list(list_a, 0)
    fmt.print("With 0 appended: "); list.print(with_zero)

    // Take and drop
    first_two := list.take(combined, 2)
    fmt.print("First 2: "); list.print(first_two)

    rest := list.drop(combined, 2)
    fmt.print("After dropping 2: "); list.print(rest)

    // Cleanup
    list.destroy(list_a)
    list.destroy(list_b)
    list.destroy(combined)
    list.destroy(reversed)
    list.destroy(with_zero)
    list.destroy(first_two)
    list.destroy(rest)
}

Memory Management

Important: This library uses dynamic memory allocation. You must call destroy() on every list when you're done with it to prevent memory leaks.

// Good practice
my_list := list.from_array([]int{1, 2, 3})
// ... use the list ...
list.destroy(my_list)  // Always clean up!

// For derived lists
doubled := list.map_list(my_list, double_func)
// ... use doubled ...
list.destroy(my_list)  // Clean up original
list.destroy(doubled)  // Clean up derived list

Memory Safety Notes

  • Each list operation that returns a new list allocates new memory
  • Original lists are never modified (immutable)
  • Always pair creation with destruction
  • Use custom allocators if needed by passing the allocator parameter

Testing

Run the test suite to verify functionality:

odin test .

The test suite covers:

  • Basic list operations
  • Edge cases (empty lists, single elements)
  • Memory management
  • Type safety
  • All higher-order functions

Design Philosophy

This list implementation follows functional programming principles:

  1. Immutability: Lists are never modified in place
  2. Persistence: Operations return new lists, original data is preserved
  3. Composability: Functions can be easily combined and chained
  4. Type Safety: Full generic support with compile-time type checking
  5. Memory Explicit: Clear ownership and cleanup requirements

Performance Characteristics

  • Head access: O(1)
  • Tail access: O(1)
  • Length calculation: O(n)
  • Element access by index: O(n)
  • Cons (prepend): O(1)
  • Append: O(n)
  • Map/Filter: O(n)
  • Reverse: O(n)
  • Fold: O(n)

For performance-critical applications requiring random access, consider using dynamic arrays instead.

License

This implementation is provided as-is for educational and practical use in Odin projects.

Package Info
Version
v8727f00
License
Unknown
Author
@fredericcormier
Type
library
Forks
1
Created
11 months ago
Updated
11 months ago
Health
maintained
has releases
has readme
has license
Maintainer
fredericcormier
fredericcormier
Maintainer
Activity
last 56 weeks