# Stack — foundational LIFO stack for Bend.
# Publish entry for this package. Depends only on Base (does not reimplement List).
#
# Encoding: a thin wrapper over List with the top at the list head.
# to_list is top-first (list head = stack top), not bottom-first.
# Quantity: Stack<a, A> is Kind(a), same convention as List/Maybe.
import Base

type Stack<a, -A: Kind(a)> is Kind(a):
  S{data: List<a, A>}

# Pop view: head + remaining stack.
type Stack.Pop<a, -A: Kind(a)> is Kind(a):
  HD{head: A, rest: Stack<a, A>}

def Stack.empty(a, -A: Kind(a)) -> Stack<a, A>:
  S{Nil{}}

def Stack.push(a, -A: Kind(a), s: Stack<a, A>, x: A) -> Stack<a, A>:
  match s:
    case S{xs}:
      S{x <> xs}

def Stack.pop.go(a, -A: Kind(a), s: Stack<a, A>) -> Maybe<a, Stack.Pop<a, A>>:
  match s:
    case S{xs}:
      match xs:
        case Nil{}:
          None{}
        case h <> t:
          Some{HD{h, S{t}}}

def Stack.pop(a, -A: Kind(a), s: Stack<a, A>) -> Maybe<a, Stack.Pop<a, A>>:
  Stack.pop.go(a, A, s)

def Stack.peek.go(a, -A: Kind(a), s: Stack<a, A>) -> Maybe<a, A>:
  match s:
    case S{xs}:
      match xs:
        case Nil{}:
          None{}
        case h <> t:
          Some{h}

def Stack.peek(a, -A: Kind(a), s: Stack<a, A>) -> Maybe<a, A>:
  Stack.peek.go(a, A, s)

def Stack.is_empty(a, -A: Kind(a), s: Stack<a, A>) -> Bool:
  match s:
    case S{xs}:
      List.is_empty(a, A, xs)

def Stack.length(a, -A: Kind(a), s: Stack<a, A>) -> Nat:
  match s:
    case S{xs}:
      List.length(a, A, xs)

def Stack.to_list(a, -A: Kind(a), s: Stack<a, A>) -> List<a, A>:
  match s:
    case S{xs}:
      xs

def Stack.from_list(a, -A: Kind(a), xs: List<a, A>) -> Stack<a, A>:
  S{xs}