Linked List
Build a list that is read and written at both ends, push and pop at the back, unshift and shift at the front, that counts its values and deletes the first one equal to a given value.
Adapted from Exercism’s problem specification (MIT). Listed under Collections & Algorithms.
// FILE: linked_list.nomi
//# A list read and written at both ends, as a doubly linked list is.
/// A list that is read and written at both ends: `push` and `pop` at the
/// back, `unshift` and `shift` at the front. It is a value, so every
/// operation answers a list.
///
/// The values are two lists, the front ones in order and the back ones
/// newest first, so each end is the head of one of them. An end that runs
/// out takes the other list's values, reversed.
pub opaque struct LinkedList<T>
front: List<T>
back: List<T>
end
impl LinkedList<T>
/// A list with no values.
pub fn new() -> LinkedList<T>
{front: [], back: []}
end
/// `list` with `value` after its last value.
pub fn push(list: LinkedList<T>, value: T) -> LinkedList<T>
{..list, back: [value, ..]}
end
/// `list` with `value` before its first value.
pub fn unshift(list: LinkedList<T>, value: T) -> LinkedList<T>
{..list, front: [value, ..]}
end
/// The last value of `list` and the list without it, or `None` when it is
/// empty.
pub fn pop(list: LinkedList<T>) -> Maybe<(T, LinkedList<T>)>
case list.back
[last, ..back] ->
Some((last, {..list, back:}))
[] ->
case Iter.reverse(list.front)
[last, ..back] -> Some((last, {front: [], back:}))
[] -> None
end
end
end
/// The first value of `list` and the list without it, or `None` when it
/// is empty.
pub fn shift(list: LinkedList<T>) -> Maybe<(T, LinkedList<T>)>
case list.front
[first, ..front] ->
Some((first, {..list, front:}))
[] ->
case Iter.reverse(list.back)
[first, ..front] -> Some((first, {front:, back: []}))
[] -> None
end
end
end
/// `list` without the first value equal to `value`; the same values when
/// there is none.
pub fn delete(list: LinkedList<T>, value: T) -> LinkedList<T> where T: Equatable
{front: list |> Iter.to_list() |> List.remove(value), back: []}
end
end
impl Iter<T> for LinkedList<T>
/// Walks the list from its first value to its last.
fn each_while(list: LinkedList<T>, yield: (T) -> Bool) -> Bool
Iter.each_while(list.front, yield)
and (list.back |> Iter.reverse() |> Iter.each_while(yield))
end
end
// FILE: linked_list_test.nomi
import linked_list.LinkedList
/// One canonical operation and what it should answer: a push or an unshift,
/// a pop or a shift of a given value or one that finds the list empty, a
/// count, a delete.
enum Step
Push Int
Pop Int
PopFails
Shift Int
ShiftFails
Unshift Int
Count Int
Delete Int
end
/// Runs each step's operation on an empty list, 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(steps: List<Step>) -> List<Step>
(_list, happened) =
steps
|> Iter.map_reduce(LinkedList.new(), fn list, step ->
case step
.Push(value) ->
(LinkedList.push(list, value), Step.Push(value))
.Unshift(value) ->
(LinkedList.unshift(list, value), .Unshift(value))
.Pop(_) or .PopFails ->
case LinkedList.pop(list)
Some((value, rest)) -> (rest, .Pop(value))
None -> (list, .PopFails)
end
.Shift(_) or .ShiftFails ->
case LinkedList.shift(list)
Some((value, rest)) -> (rest, .Shift(value))
None -> (list, .ShiftFails)
end
.Count(_) ->
(list, .Count(Iter.count(list)))
.Delete(value) ->
(LinkedList.delete(list, value), .Delete(value))
end
end)
happened
end
test "linked list"
[
("pop gets element from the list", [Step.Push(7), .Pop(7)]),
(
"push/pop respectively add/remove at the end of the list",
[.Push(11), .Push(13), .Pop(13), .Pop(11)],
),
("shift gets an element from the list", [.Push(17), .Shift(17)]),
("shift gets first element from the list", [.Push(23), .Push(5), .Shift(23), .Shift(5)]),
(
"unshift adds element at start of the list",
[.Unshift(23), .Unshift(5), .Shift(5), .Shift(23)],
),
(
"pop, push, shift, and unshift can be used in any order",
[
.Push(1),
.Push(2),
.Pop(2),
.Push(3),
.Shift(1),
.Unshift(4),
.Push(5),
.Shift(4),
.Pop(5),
.Shift(3),
],
),
("count an empty list", [.Count(0)]),
("count a list with items", [.Push(37), .Push(1), .Count(2)]),
(
"count is correct after mutation",
[
.Push(31),
.Count(1),
.Unshift(43),
.Count(2),
.Shift(43),
.Count(1),
.Pop(31),
.Count(0),
],
),
(
"popping to empty doesn't break the list",
[.Push(41), .Push(59), .Pop(59), .Pop(41), .Push(47), .Count(1), .Pop(47)],
),
(
"shifting to empty doesn't break the list",
[.Push(41), .Push(59), .Shift(41), .Shift(59), .Push(47), .Count(1), .Shift(47)],
),
("deletes the only element", [.Push(61), .Delete(61), .Count(0)]),
(
"deletes the element with the specified value from the list",
[.Push(71), .Push(83), .Push(79), .Delete(83), .Count(2), .Pop(79), .Shift(71)],
),
(
"deletes the element with the specified value from the list, re-assigns tail",
[.Push(71), .Push(83), .Push(79), .Delete(83), .Count(2), .Pop(79), .Pop(71)],
),
(
"deletes the element with the specified value from the list, re-assigns head",
[.Push(71), .Push(83), .Push(79), .Delete(83), .Count(2), .Shift(71), .Shift(79)],
),
(
"deletes the first of two elements",
[.Push(97), .Push(101), .Delete(97), .Count(1), .Pop(101)],
),
(
"deletes the second of two elements",
[.Push(97), .Push(101), .Delete(101), .Count(1), .Pop(97)],
),
(
"delete does not modify the list if the element is not found",
[.Push(89), .Delete(103), .Count(1)],
),
(
"deletes only the first occurrence",
[
.Push(73),
.Push(9),
.Push(9),
.Push(107),
.Delete(9),
.Count(3),
.Pop(107),
.Pop(9),
.Pop(73),
],
),
]
|> subtests (description, steps), description
assert replay(steps) == steps
end
end
// Not canonical: the canonical cases never pop or shift an empty list.
test "pop and shift on an empty list find nothing"
steps = [Step.PopFails, .ShiftFails, .Push(1), .Shift(1), .PopFails]
assert replay(steps) == steps
endok linked list (19 cases)
ok pop and shift on an empty list find nothing
test result: ok. 20 passed, 0 failed
How it’s written
Section titled “How it’s written”- Adapted: the exercise asks for a doubly linked list, whose nodes point both ways and are edited in place. Nomi values cannot change, so no node can point back at one built after it; the port keeps the operations and their cost instead, as a persistent double-ended list. Each operation answers a new list.
LinkedList<T>is an opaque struct of twoLists, the front values in order and the back values newest first, so both ends are a list head:push,unshiftand apoporshiftthat finds its end non-empty take constant time. An end that runs out reverses the other list once, which every value pays at most once on its way through.popandshiftanswerMaybe<(T, LinkedList<T>)>, the value and the list without it, withNonefor an empty list. The canonical data never empties a list too far, and the test file adds one case, marked not canonical, that does.impl Iter<T> for LinkedList<T>walks the front, then the back reversed, so the count is std’sIter.countanddeletereads the values in order withIter.to_list.deletetakes out the first equal value withList.removeand answers the rest as one front list.- The canonical cases are lists of operations, so the test file follows circular-buffer and simple-linked-list: each is a list of
Steps (Push(7),Pop(7),Shift(17),Unshift(23),Count(2),Delete(83)),replayruns them on an empty list with oneIter.map_reduce, and each row assertsreplay(steps) == steps. Where a canonical pop or shift gives no expected value, its step names the value it takes. - The 19 canonical cases are one
subteststable named by the description column.