pqueue-mtl-1.0: Data/Queue/Stack.hs

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}

-- | A basic implementation of a stack implementing the 'Queue' abstraction.
module Data.Queue.Stack (Stack) where

import Data.Monoid
import Data.Queue.Class

data Stack e = S {elts :: {-# UNPACK #-} !Int, getS :: [e]}

instance Queuelike (Stack e) e where
	insert x (S n xs) = S (n+1) (x:xs)
	extract (S (n+1) (x:xs)) = Just (x, S n xs)
	extract _ = Nothing
	empty = S 0 []
	isEmpty = null . getS
	size = elts
	toList = getS
	S n1 s1 `merge` S n2 s2 = S (n1 + n2) (s2 ++ s1)

instance Monoid (Stack e) where
	mempty = empty
	mappend = merge