[Haskell-beginners] OrdList implementation

Mark Carter alt.mcarter at gmail.com
Thu Nov 12 12:41:18 UTC 2015

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
     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.

More information about the Beginners mailing list