<div dir="ltr"><div><div><div><div>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?<br><br></div><a href="https://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Map-Strict.html">https://hackage.haskell.org/package/containers-0.5.6.3/docs/Data-Map-Strict.html</a>  :: Data.Map uses a ordered balanced binary tree implementation for storing and retrieving key value pairs.  <br><br></div>Now, with that out of the way,<br><br></div>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).<br><br></div>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 <a href="http://dev.stephendiehl.com/hask/">http://dev.stephendiehl.com/hask/</a> and learn you a haskell for great good).<br><br></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Nov 12, 2015 at 6:11 PM, Mark Carter <span dir="ltr"><<a href="mailto:alt.mcarter@gmail.com" target="_blank">alt.mcarter@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I am trying to implement "OrdList", which is a list that is guaranteed to be ordered. Here's my implementation so far:<br>
<br>
module OrdList (empty, fromList, insert, toList, OrdList(OrdList)) where<br>
import Data.List as L (span)<br>
<br>
data OrdList a = OrdList [a] deriving (Show)<br>
<br>
<br>
empty :: OrdList a<br>
empty = OrdList []<br>
<br>
<br>
insert :: (Ord a) => a -> OrdList a -> OrdList a<br>
insert x ol =<br>
  let -- OrdList xs = ol<br>
      (before, after) = L.span (\el -> el <= x) $ toList xs<br>
  in<br>
    OrdList $  before ++ [x] ++ after<br>
<br>
fromList :: Ord a => [a] -> OrdList a<br>
fromList xs =<br>
  if null xs then empty else insert (head xs) (fromList $ tail xs)<br>
<br>
toList :: OrdList t -> [t]<br>
toList xs =<br>
  let OrdList xs' = xs in xs'<br>
<br>
<br>
<br>
It "works", but no doubt there's plenty to dislike about it. Some specific questions I have in mind:<br>
1. Should OrdList be best implemented as a class, data, or newtype? If so, what changes need to be made?<br>
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.<br>
<br>
<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div><br></div>