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.
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....
:: 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
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
participants (2)
-
akash g -
Mark Carter