Skip to content

Simple Linked List

Build a singly linked list that is last in, first out: count it, push and pop values, peek at the head, list its values and reverse it.

Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.

// FILE: simple_linked_list.nomi
//# A singly linked list, used as a stack.

/// A singly linked list that is last in, first out: `push` puts a value at
/// the head, and `pop` and `peek` read the head. It is a value, so every
/// operation answers a list and shares the nodes it did not change.
pub enum LinkedList<T>
    Empty
    Node {value: T, next: LinkedList<T>}
end

/// Why a value cannot be read.
pub enum Error
    EmptyList
end

impl LinkedList<T>
    /// The list that pushing `values` one after another onto an empty list
    /// builds, so the last of them is at the head.
    pub fn from(values: List<T>) -> LinkedList<T>
        Iter.reduce(values, LinkedList.Empty, LinkedList.push)
    end

    /// `list` with `value` at its head.
    pub fn push(list: LinkedList<T>, value: T) -> LinkedList<T>
        .Node{value:, next: list}
    end

    /// The value at the head of `list` and the list after it, or
    /// `EmptyList`.
    pub fn pop(list: LinkedList<T>) -> Result<(T, LinkedList<T>), Error>
        case list
            .Empty               -> Err(.EmptyList)
            .Node{value:, next:} -> Ok((value, next))
        end
    end

    /// The value at the head of `list`, or `EmptyList`.
    pub fn peek(list: LinkedList<T>) -> Result<T, Error>
        case list
            .Empty        -> Err(.EmptyList)
            .Node{value:} -> Ok(value)
        end
    end

    /// `list` with its values in the opposite order.
    pub fn reverse(list: LinkedList<T>) -> LinkedList<T>
        Iter.reduce(list, LinkedList.Empty, LinkedList.push)
    end
end

impl Iter<T> for LinkedList<T>
    /// Walks the list from its head, so `Iter.to_list` answers the values in
    /// the order `pop` would.
    fn each_while(list: LinkedList<T>, yield: (T) -> Bool) -> Bool
        case list
            .Empty               -> True
            .Node{value:, next:} -> yield(value) and each_while(next, yield)
        end
    end
end

// FILE: simple_linked_list_test.nomi
import simple_linked_list.LinkedList

/// One canonical operation and what it should answer: a count, a pop or a
/// peek of a given value or one that fails, a push, the values as a list, a
/// reverse.
enum Step
    Count Int
    Pop Int
    PopFails
    Push Int
    Peek Int
    PeekFails
    ToList List<Int>
    Reverse
end

/// Runs each step's operation on the list built from `values`, in turn, and
/// answers the steps as they happened. A list that does what every step
/// says answers the steps it was given.
fn replay(values: List<Int>, steps: List<Step>) -> List<Step>
    (_list, happened) =
        steps
        |> Iter.map_reduce(LinkedList.from(values), fn list, step ->
            case step
                .Count(_) ->
                    (list, Step.Count(Iter.count(list)))

                .Pop(_) or .PopFails ->
                    case LinkedList.pop(list)
                        Ok((value, rest)) -> (rest, .Pop(value))
                        Err(_)            -> (list, .PopFails)
                    end

                .Push(value) ->
                    (LinkedList.push(list, value), .Push(value))

                .Peek(_) or .PeekFails ->
                    case LinkedList.peek(list)
                        Ok(value) -> (list, .Peek(value))
                        Err(_)    -> (list, .PeekFails)
                    end

                .ToList(_) ->
                    (list, .ToList(Iter.to_list(list)))

                .Reverse ->
                    (LinkedList.reverse(list), .Reverse)
            end
        end)

    happened
end

test "count"
    [
        ("Empty list has length of zero",     [],        [Step.Count(0)]),
        ("Singleton list has length of one",  [1],       [.Count(1)]),
        ("Non-empty list has correct length", [1, 2, 3], [.Count(3)]),
    ]
    |> subtests (description, values, steps), description
        assert replay(values, steps) == steps
    end
end

test "pop"
    [
        ("Pop from empty list is an error", [], [Step.PopFails]),
        ("Can pop from singleton list", [1], [.Pop(1)]),
        ("Can pop from non-empty list", [1, 2], [.Pop(2)]),
        ("Can pop multiple items", [1, 2], [.Pop(2), .Pop(1)]),
        ("Pop updates the count", [1, 2], [.Count(2), .Pop(2), .Count(1), .Pop(1), .Count(0)]),
    ]
    |> subtests (description, values, steps), description
        assert replay(values, steps) == steps
    end
end

test "push"
    [
        ("Can push to an empty list",    [],     [Step.Push(1)]),
        ("Can push to a non-empty list", [1, 2], [.Push(3)]),
        ("Push updates count",           [1, 2], [.Push(3), .Count(3)]),
        (
            "Push and pop",
            [],
            [.Push(1), .Push(2), .Pop(2), .Push(3), .Count(2), .Pop(3), .Pop(1), .Count(0)],
        ),
    ]
    |> subtests (description, values, steps), description
        assert replay(values, steps) == steps
    end
end

test "peek"
    [
        ("Peek on empty list is an error", [],     [Step.PeekFails]),
        ("Can peek on singleton list",     [1],    [.Peek(1)]),
        ("Can peek on non-empty list",     [1, 2], [.Peek(2)]),
        ("Peek does not change the count", [1, 2], [.Peek(2), .Count(2)]),
        (
            "Can peek after a pop and push",
            [],
            [.Push(1), .Push(2), .Peek(2), .Pop(2), .Peek(1), .Push(3), .Peek(3)],
        ),
    ]
    |> subtests (description, values, steps), description
        assert replay(values, steps) == steps
    end
end

test "toList LIFO"
    [
        ("Empty linked list to list is empty", [],        [Step.ToList([])]),
        ("To list with multiple values",       [1, 2, 3], [.ToList([3, 2, 1])]),
        (
            "To list after a pop",
            [],
            [.Push(1), .Push(2), .Push(3), .Pop(3), .Push(4), .ToList([4, 2, 1])],
        ),
    ]
    |> subtests (description, values, steps), description
        assert replay(values, steps) == steps
    end
end

test "reverse"
    [
        ("Reversed empty list has same values",  [],  [Step.Reverse, .ToList([])]),
        ("Reversed singleton list is same list", [1], [.Reverse, .ToList([1])]),
        (
            "Reversed non-empty list is reversed",
            [1, 2, 3],
            [.Reverse, .Count(3), .Pop(1), .Pop(2), .Pop(3)],
        ),
        ("Double reverse", [1, 2, 3], [.Reverse, .Reverse, .Pop(3), .Pop(2), .Pop(1)]),
    ]
    |> subtests (description, values, steps), description
        assert replay(values, steps) == steps
    end
end
  • LinkedList<T> is a generic enum, Empty or a Node with a value and the next list. Nomi values cannot change, so it is a persistent list: push answers a new head over the old list, pop answers the head’s value and the list after it, and every list shares the nodes below its head with the list it came from.
  • pop and peek answer Result, with Error.EmptyList for an empty list, the canonical “list is empty” error.
  • impl Iter<T> for LinkedList<T> walks the list from the head, so counting and listing the values are std’s Iter.count and Iter.to_list, called on the list from the tests, and reverse is Iter.reduce(list, LinkedList.Empty, LinkedList.push). Iter.count walks the list each time, as a singly linked list without a stored length does.
  • The canonical data has two mutually exclusive groups for the list’s values, last in first out ([3, 2, 1] for a list built from [1, 2, 3]) and first in first out. This port takes the first, which is the order pop answers and Iter walks, and leaves out the three first-in-first-out cases.
  • The canonical cases are lists of operations, so the test file follows circular-buffer: each is a list of Steps (Count(2), Pop(2), PopFails, Push(3), Peek(1), PeekFails, ToList([3, 2, 1]), Reverse), replay runs them on the list built from the case’s initial values with one Iter.map_reduce, and each row asserts replay(values, steps) == steps.
  • Each canonical group is a test holding one subtests table. Two cases that newer ones reimplement are left out: the first “Can push to an empty list”, which the canonical data writes with no initial values at all, and the first “Reversed non-empty list is reversed”, which the newer one extends with a count.