Nanyx
PlaygroundPackages

stack

Immutable stacks, last in, first out

Import it as nanyx/stack. A Stack is a list read from one end: push puts a value on top and pop takes it off, each in constant time, and each gives back a new stack, leaving the one it was given as it was. For a stack that changes in place inside a memory block, see MStack.

import nanyx/stack

def stack = Stack[2, 1] \push(3)

match Stack.pop(stack)
  | #some(top, rest) -> println("{top} {Stack.toList(rest)}") -- 3 [2, 1]
  | #none -> println("empty")

Reference

Immutable stacks: last in, first out.

A Stack(a) is a list read from one end: Stack.push puts a value on top and Stack.pop takes it off, each in constant time. Nothing about a stack changes once it is made: each of them gives back a new stack, which shares the rest of its values with the one it was made from, so the old one still holds what it held. For a stack that changes in place, see MStack.

Two stacks are == when they hold equal values in the same order, and a stack can be a map’s key when its values can. Stack.toString writes one as Stack[3, 2, 1], the top first.

Each function is attached to Stack, so with import nanyx/stack it is called as Stack.push(s, 5), or as s \push(5). A literal makes one, the first value on top: Stack[3, 2, 1], or [3, 2, 1] where a stack is expected.

Stack

type Stack(a) = protected list(a)

Stack.empty

def Stack.empty: Stack(a)

The stack with nothing on it.

Stack.fromList

def Stack.fromList: list(a) -> Stack(a)

A stack holding xs, the first of them on top.

Stack.fromArray

def Stack.fromArray: array(a) -> Stack(a)

A stack holding xs, the first of them on top. What a literal builds a stack with, Stack[3, 2, 1], or [3, 2, 1] where a stack is expected.

Stack.fromSeq

def Stack.fromSeq: [c] ([c] seq(a)) -> Stack(a)

A stack holding the elements of s, pulled now, the first of them on top. It requires the contexts the sequence’s steps do.

Stack.build

def Stack.build: [c, d] ([c] () -> [d] seq(a)) -> Stack(a)

A stack of what block yields, the first on top. The same as seq(block) \Stack.fromSeq.

Stack.push

def Stack.push: Stack(a), a -> Stack(a)

stack with value on top of it.

Stack.pop

def Stack.pop: Stack(a) -> #some(a, Stack(a)) | #none

The value on top of stack and the stack below it, or #none when it is empty.

Stack.peek

def Stack.peek: Stack(a) -> #some(a) | #none

The value on top of stack, or #none when it is empty.

Stack.isEmpty

def Stack.isEmpty: Stack(a) -> bool

Whether stack has nothing on it.

Stack.length

def Stack.length: Stack(a) -> int

How many values are on stack. It counts them, so it takes time in proportion to how many there are.

Stack.toSeq

def Stack.toSeq: Stack(a) -> seq(a)

The values on stack, the top one first, as a sequence. A stack is Iterable by it, so a for loop walks one.

Stack.toList

def Stack.toList: Stack(a) -> list(a)

The values on stack, the top one first.

Stack.toString

def Stack.toString: [ToString(a)] Stack(a) -> string

stack as its literal is written, the top first: Stack[3, 2, 1], and Stack[] when it is empty.

Stack.reduce

def Stack.reduce: [c] Stack(a), ([c] (a, a) -> a) -> #some(a) | #none

The elements of s, from the top, combined with f, in order, starting from the first: a stack of 1 to 5 reduced with { * } is #some(120), and an empty one, having no first element, gives #none. To start from another value, use list.fold.