Just a note on the data structure.  Wouldn't a binary tree (a balanced one; red-black, avl etc) give a logarithmic time constant for insertion while a list will give you a worst case bound of n, n being the length of the list?

https://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Map-Strict.html  :: Data.Map uses a ordered balanced binary tree implementation for storing and retrieving key value pairs. 

Now, with that out of the way,

For 1, you are defining OrdList a to be a new data type (or type with a data constructor).  Just to make sure users of this package cannot construct ill-formed OrdList, you can hide the constructor and provide your custom constructor (like fromList and its ilk).

For 2., I don't know what you mean but OrdList is a datatype or rather a type constructor which takes an additional concrete type to form a concrete type.  In other words, OrdList is of the kind (*->*).  Lookup kinds (wikibooks is good for this and so are http://dev.stephendiehl.com/hask/ and learn you a haskell for great good).


On Thu, Nov 12, 2015 at 6:11 PM, Mark Carter <alt.mcarter@gmail.com> wrote:
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.


_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners