module Data.SortedList (
SortedList
, toSortedList
, fromSortedList
, singleton
, repeat
, replicate
, iterate
, uncons
, insert
, take
, drop
, splitAt
, filter
, null
, elemOrd
, map
, nub
) where
import Prelude hiding
( take, drop, splitAt, filter
, repeat, replicate, iterate
, null, map
#if !MIN_VERSION_base(4,8,0)
, foldr
#endif
)
import qualified Data.List as List
import Data.Monoid ((<>))
import Data.Foldable (toList)
#if !MIN_VERSION_base(4,8,0)
import Data.Monoid (Monoid (..))
import Data.Foldable (Foldable, foldr)
#endif
newtype SortedList a = SortedList [a]
instance Show a => Show (SortedList a) where
show = show . fromSortedList
null :: SortedList a -> Bool
null = List.null . fromSortedList
uncons :: SortedList a -> Maybe (a, SortedList a)
uncons (SortedList []) = Nothing
uncons (SortedList (x:xs)) = Just (x, SortedList xs)
toSortedList :: Ord a => [a] -> SortedList a
toSortedList = SortedList . List.sort
fromSortedList :: SortedList a -> [a]
fromSortedList (SortedList xs) = xs
mergeSortedLists :: Ord a => [a] -> [a] -> [a]
mergeSortedLists xs [] = xs
mergeSortedLists [] ys = ys
mergeSortedLists (x:xs) (y:ys) =
if x <= y
then x : mergeSortedLists xs (y:ys)
else y : mergeSortedLists (x:xs) ys
instance Ord a => Monoid (SortedList a) where
mempty = SortedList []
mappend (SortedList xs) (SortedList ys) = SortedList $ mergeSortedLists xs ys
singleton :: a -> SortedList a
singleton x = SortedList [x]
repeat :: a -> SortedList a
repeat = SortedList . List.repeat
replicate :: Int -> a -> SortedList a
replicate n = SortedList . List.replicate n
iterate :: Ord a => (a -> a) -> a -> SortedList a
iterate f x = SortedList $ x : go x (f x)
where
go prev fprev =
if prev <= fprev
then fprev : go fprev (f fprev)
else []
insert :: Ord a => a -> SortedList a -> SortedList a
insert x xs = singleton x <> xs
take :: Int -> SortedList a -> SortedList a
take n = fst . splitAt n
drop :: Int -> SortedList a -> SortedList a
drop n = snd . splitAt n
splitAt :: Int -> SortedList a -> (SortedList a, SortedList a)
splitAt n (SortedList xs) =
let (ys,zs) = List.splitAt n xs
in (SortedList ys, SortedList zs)
filter :: (a -> Bool) -> SortedList a -> SortedList a
filter f (SortedList xs) = SortedList $ List.filter f xs
elemOrd :: Ord a => a -> SortedList a -> Bool
elemOrd a (SortedList l) = go l
where
go (x:xs) =
case compare a x of
GT -> go xs
EQ -> True
_ -> False
go _ = False
nub :: Eq a => SortedList a -> SortedList a
nub (SortedList l) = SortedList $ go l
where
go (x:y:xs) = if x == y then go (x:xs) else x : go (y:xs)
go xs = xs
instance Foldable SortedList where
foldr f e (SortedList xs) = foldr f e xs
#if MIN_VERSION_base(4,8,0)
toList = fromSortedList
minimum (SortedList xs) =
case xs of
x : _ -> x
_ -> error "SortedList.minimum: empty list"
maximum (SortedList xs) =
case xs of
[] -> error "SortedList.maximum: empty list"
_ -> last xs
#endif
map :: Ord b => (a -> b) -> SortedList a -> SortedList b
map f = foldr (insert . f) mempty