In today’s Programming Praxis exercise, our goal is to create s stack-like data structure that can push, pop and give the minimum element in the stack in O(1). Let’s get started, shall we?
To represent a stack, we can use a basic linked list. We’ll need two of them, one to hold the elements and one to hold the consecutive minimums. I’ve put them in a tuple, though a datatype declaration would’ve been an option as well.
An empty minstack is just two empty lists.
empty :: ([a], [a1]) empty = ([], [])
When pusing a new element we add it at the front of the list and optionally in the list of minimums as well.
push :: Ord a => a -> ([a], [a]) -> ([a], [a]) push x (ms,xs) = (if null ms || x < head ms then x:ms else ms, x: xs)
To pop, we return the popped element (if any) and the new minstack.
pop :: Eq a => ([a], [a]) -> (Maybe a, ([a], [a])) pop (m:ms,x:xs) = (Just x, (if m == x then ms else m:ms, xs)) pop s = (Nothing, s)
To find the minimum element we simple take the first element in the list of minimums.
min' :: ([a], [a]) -> Maybe a min' (m:_, _) = Just m min' _ = Nothing
Some tests to see if everything is working properly:
main :: IO () main = do let top = fst . pop let pop' = snd . pop let a = push 5 . push 4 $ push 3 empty print $ top a == Just 5 print $ min' a == Just 3 let b = push 2 $ push 1 a print $ top b == Just 2 print $ min' b == Just 1 let c = pop' . pop' $ pop' b print $ top c == Just 4 print $ min' c == Just 3 let d = pop' $ pop' c print $ d == empty
Tags: bonsai, code, Haskell, kata, min stack, minstack, praxis, programming
