Stack

{-| A simple implementation of stacks in Haskell -}

module Stack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
data Stack = Empty | Push Int Stack
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = Empty
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty Empty = True
isEmpty (Push _ _) = False
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push = Push
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top (Push x s) = x
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop (Push x s) = s

-- | Compute size of stack
size :: Stack -> Int
size Empty = 0
size (Push _ s) = 1 + size s

{-| 

A leaky list-based implementation of stacks in Haskell.
That is, the representation type is not hidden.

-}

module LeakyListStack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
type Stack = [Int]
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = []
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty = null
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push = (:)
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top = head
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop = tail

-- | Compute size of stack
size :: Stack -> Int
size = length

{-| 

An opaque list-based implementation of stacks in Haskell.
That is, the representation type is hidden. 

-}

module OpaqueListStack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
newtype Stack = Stack { getStack :: [Int] }
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = Stack []
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty = null . getStack
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push x s = Stack ( x : getStack s)
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top = head . getStack
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop = Stack . tail . getStack

-- | Compute size of stack
size :: Stack -> Int
size = length . getStack

{-| 

An opaque list-based implementation of stacks in Haskell.
That is, the representation type is hidden.
The size of the stack is readily maintained.
Thus, the size can be returned with traversing the stack.

-}

module FastListStack (
  Stack,
  empty,
  isEmpty,
  push,
  top,
  pop,
  size
) where

-- | Data structure for representation of stacks
data Stack = Stack { getStack :: [Int], getSize :: Int }
 
{- Operations on stacks -}
 
-- | Return the empty stack
empty :: Stack
empty = Stack [] 0
 
-- | Test for the empty stack
isEmpty :: Stack -> Bool
isEmpty = null . getStack
 
-- | Push an element onto the stack
push :: Int -> Stack -> Stack
push x s
  = Stack { 
      getStack = x : getStack s,
      getSize = getSize s + 1
    }
 
-- | Retrieve the top-of-stack, if available
top :: Stack -> Int
top = head . getStack
 
-- | Remove the top-of-stack, if available
pop :: Stack -> Stack
pop s
  = Stack {
      getStack = tail (getStack s),
      getSize = getSize s - 1
    }

-- | Compute size of stack
size :: Stack -> Int
size = getSize