X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=compiler%2Futils%2FOrdList.lhs;h=74c9ed8d0b1e2191b160a9d6601009b07cbe1ca7;hb=f4b727487a65e6b611bbaafbd2207bd63a8df706;hp=7f22b38e495a0af306f935f7b9aa8fa8a6696cfe;hpb=0065d5ab628975892cea1ec7303f968c3338cbe1;p=ghc-hetmet.git

diff --git a/compiler/utils/OrdList.lhs b/compiler/utils/OrdList.lhs
index 7f22b38..74c9ed8 100644
--- a/compiler/utils/OrdList.lhs
+++ b/compiler/utils/OrdList.lhs
@@ -1,4 +1,5 @@
 %
+% (c) The University of Glasgow 2006
 % (c) The AQUA Project, Glasgow University, 1993-1998
 %
 
@@ -11,7 +12,7 @@ can be appended in linear time.
 module OrdList (
 	OrdList, 
         nilOL, isNilOL, unitOL, appOL, consOL, snocOL, concatOL,
-        fromOL, toOL, foldrOL, foldlOL
+        mapOL, fromOL, toOL, foldrOL, foldlOL
 ) where
 
 infixl 5  `appOL`
@@ -19,8 +20,9 @@ infixl 5  `snocOL`
 infixr 5  `consOL`
 
 data OrdList a
-  = Many [a]
-  | Two (OrdList a) (OrdList a)
+  = Many [a]        -- Invariant: non-empty
+  | Two (OrdList a) -- Invariant: non-empty
+        (OrdList a) -- Invariant: non-empty
   | One  a
   | None
 
@@ -35,21 +37,21 @@ concatOL :: [OrdList a] -> OrdList a
 
 nilOL        = None
 unitOL as    = One as
-snocOL as b  = Two as (One b)
-consOL a  bs = Two (One a) bs
-concatOL aas = foldr Two None aas
+snocOL None b    = One b
+snocOL as   b    = Two as (One b)
+consOL a    None = One a
+consOL a    bs   = Two (One a) bs
+concatOL aas = foldr appOL None aas
 
-isNilOL None        = True
-isNilOL (One _)     = False
-isNilOL (Two as bs) = isNilOL as && isNilOL bs
-isNilOL (Many xs)   = null xs
+isNilOL None = True
+isNilOL _    = False
 
 appOL None bs   = bs
 appOL as   None = as
 appOL as   bs   = Two as bs
 
 mapOL :: (a -> b) -> OrdList a -> OrdList b
-mapOL f None = None
+mapOL _ None = None
 mapOL f (One x) = One (f x)
 mapOL f (Two x y) = Two (mapOL f x) (mapOL f y)
 mapOL f (Many xs) = Many (map f xs)
@@ -58,13 +60,13 @@ instance Functor OrdList where
   fmap = mapOL
 
 foldrOL :: (a->b->b) -> b -> OrdList a -> b
-foldrOL k z None        = z
+foldrOL _ z None        = z
 foldrOL k z (One x)     = k x z
 foldrOL k z (Two b1 b2) = foldrOL k (foldrOL k z b2) b1
 foldrOL k z (Many xs)   = foldr k z xs
 
 foldlOL :: (b->a->b) -> b -> OrdList a -> b
-foldlOL k z None        = z
+foldlOL _ z None        = z
 foldlOL k z (One x)     = k z x
 foldlOL k z (Two b1 b2) = foldlOL k (foldlOL k z b1) b2
 foldlOL k z (Many xs)   = foldl k z xs
@@ -76,8 +78,9 @@ fromOL ol
         flat None      rest = rest
         flat (One x)   rest = x:rest
         flat (Two a b) rest = flat a (flat b rest)
-	flat (Many xs) rest = xs ++ rest
+        flat (Many xs) rest = xs ++ rest
 
 toOL :: [a] -> OrdList a
+toOL [] = None
 toOL xs = Many xs
 \end{code}