I am trying to implement "OrdList", which is a list that is guaranteed
to be ordered. Here's my implementation so far:
module OrdList (empty, fromList, insert, toList, OrdList(OrdList)) where
import Data.List as L (span)
data OrdList a = OrdList [a] deriving (Show)
empty :: OrdList a
empty = OrdList []
insert :: (Ord a) => a -> OrdList a -> OrdList a
insert x ol =
let -- OrdList xs = ol
(before, after) = L.span (\el -> el <= x) $ toList xs
in
OrdList $ before ++ [x] ++ after
fromList :: Ord a => [a] -> OrdList a
fromList xs =
if null xs then empty else insert (head xs) (fromList $ tail xs)
toList :: OrdList t -> [t]
toList xs =
let OrdList xs' = xs in xs'
It "works", but no doubt there's plenty to dislike about it. Some
specific questions I have in mind:
1. Should OrdList be best implemented as a class, data, or newtype? If
so, what changes need to be made?
2. How comes I can't refer to OrdList as a data type? This is a problem
because I can't say that I want the type of something to be OrdList Int,
for example.
