Stack
A stack is a data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added is the first one to be removed. It operates like a stack of plates, where you can only add or remove plates from the top.
Public API
module Lib.Stack exposing
( Stack
, new
, isEmpty
, push, pop
)
-- Representation
type Stack a
-- Constructor
new : Stack
-- Query
isEmpty : Stack -> Bool
-- Modifiers
push : a -> Stack a -> Stack a
pop : Stack a -> Maybe ( a, Stack a )
Representation
I represent a stack using a list where the head of the list corresponds to the top of the stack.
type Stack a
= Stack (List a)
Constructor
The one constructor, new, creates an empty stack which is just an empty list.
new : Stack a
new =
Stack []
Query
A stack is empty if it's the empty list.
isEmpty : Stack a -> Bool
isEmpty (Stack xs) =
xs == []
Modifiers
The two main operations of a stack are push and pop.
push
It adds an element to the top of the stack.
push : a -> Stack a -> Stack a
push x (Stack xs) =
Stack (x :: xs)
pop
It removes and returns the element at the top of the stack. We have to take into account that the stack may be empty.
pop : Stack a -> Maybe ( a, Stack a )
pop (Stack xs) =
case xs of
[] ->
Nothing
x :: rest ->
Just ( x, Stack rest )