Stacks and Queues

FunctionalDataStructures.elm

-- STACKS

type Stack a = Bottom | Element a (Stack a)

push : a -> Stack a -> Stack a
push element stack = 
  Element element stack
  
  
pop : Stack a -> (Maybe a, Stack a)
pop stack = 
  case stack of
    Bottom -> (Nothing, stack)
    Element element innerStack -> (Just element, innerStack)
    

justPop : Stack a -> Stack a
justPop = snd << pop


peek : Stack a -> Maybe a 
peek stack =
  case stack of 
    Bottom -> Nothing
    Element element _ -> Just element
    
 
 
 
-- QUEUES

type Queue a = Queue (List a)

emptyQueue : Queue a
emptyQueue = Queue []

enqueue : a -> Queue a -> Queue a
enqueue element (Queue xs) = Queue (xs ++ [element])

dequeue : Queue a -> (Maybe a, Queue a)
dequeue (Queue list) =
  case list of 
    [] -> (Nothing, emptyQueue)
    x :: xs -> (Just x, Queue xs)
    

justDequeue : Queue a -> Queue a
justDequeue = snd << dequeue