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
endok count (3 cases)
ok pop (5 cases)
ok push (4 cases)
ok peek (5 cases)
ok toList LIFO (3 cases)
ok reverse (4 cases)
test result: ok. 24 passed, 0 failed
How it’s written
Section titled “How it’s written”LinkedList<T>is a generic enum,Emptyor aNodewith avalueand thenextlist. Nomi values cannot change, so it is a persistent list:pushanswers a new head over the old list,popanswers the head’s value and the list after it, and every list shares the nodes below its head with the list it came from.popandpeekanswerResult, withError.EmptyListfor 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’sIter.countandIter.to_list, called on the list from the tests, andreverseisIter.reduce(list, LinkedList.Empty, LinkedList.push).Iter.countwalks 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 orderpopanswers andIterwalks, 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),replayruns them on the list built from the case’s initial values with oneIter.map_reduce, and each row assertsreplay(values, steps) == steps. - Each canonical group is a test holding one
subteststable. 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.