Stack

A Stack is like a List but with a reduced interface. Only the top of the Stack accessible. Construct one either by calling fromList or by creating an empty Stack and pushing elements onto the stack. Access the top element using pop. Example:

State : {current: Page, back: Stack Page, forward: Stack Page }
goBack: State -> State
goBack = \state ->
    {current, back, forward} = state
    when Stack.pop back is
        Err StackWasEmpty -> state
        Ok {stack, elem} ->
            {current: elem, back: stack, forward: forward |> Stack.push current}

Stack a

empty : {} -> Stack *

Create an empty Stack.

emptyStack = Stack.empty {}

fromList : List a -> Stack a

Create a Stack from a List. The last element of the list will be the top element of the stack.

expect Stack.fromList [] == Stack.empty {}
expect Stack.fromList ["a","b"] == Stack.empty {} |> Stack.push "a" |> Stack.push "b"

push : Stack a, a -> Stack a

Push an element onto the stack.

Stack.empty {} |> Stack.push "a"

pop : Stack a -> Result { stack : Stack a, elem : a } [StackWasEmpty]

Pop the top element off of the stack. Returns the remaining stack and the retreived element if succesful, and Err StackWasEmpty if the stack was empty.

expect Stack.empty {} |> Stack.pop == Err StackWasEmpty
expect Stack.empty {} |> Stack.push "a" |> Stack.push "b" |> Stack.pop == Ok {stack: Stack.fromList ["a"], elem: "b"}

size : Stack * -> Nat

Determine the number of items on the stack.

 expect Stack.empty {} |> Stack.size == 0
 expect Stack.empty {} |> Stack.push "a" |> Stack.push "b" |> Stack.size == 2

peek : Stack a -> Result a [StackWasEmpty]

Peek at the top item of the stack.

expect Stack.empty {} |> Stack.peek == Err StackWasEmpty
expect
     Stack.empty {}
        |> Stack.push 1
        |> Stack.push 2
        |> Stack.peek
        == Ok 2

isEmpty : Stack * -> Bool

Determine if the stack is empty.

expect Stack.empty {} |> Stack.isEmpty
expect Stack.empty {} |> Stack.push 1 |> Stack.isEmpty |> Bool.not

onTopOf : Stack a, Stack a -> Stack a

Place the first stack on top of the second stack.

expect
    stack1 = Stack.empty {} |> Stack.push 1
    stack2 = Stack.empty {} |> pStack.ush 2
    stack1
        |> Stack.onTopOf stack2
        |> Stack.peek
        == Ok 1

descend : Stack a, state, (state, a -> state) -> state

Descend the stack, performing an action and accumulating a state. Analogous to walking a List.

expect Stack.empty {} |> Stack.descend 0 Num.add == 0
expect
    Stack.empty {} |> Stack.push "a" |> Stack.push "b" |> Stack.push "c"
    |> Stack.descend "" Str.concat
    == "cba"