[Haskell-beginners] OrdList implementation

[akash g]

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 at 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 at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20151112/b0a7c284/attachment.html>