From db01886e22bd80de8d94a8d5e71d2ca645cb7a8e Mon Sep 17 00:00:00 2001 From: Ian Lynagh Date: Sat, 18 Aug 2007 13:21:02 +0000 Subject: [PATCH] Add some invariants to OrdList isNilOL is now constant time, rather than possibly having to walk a tree of Two's. Compiling J.hs from trac #1136 now makes 10302 isNilOL calls rather than 50050152. It's gone from 10.8% time to being unlisted (i.e. <= 0.1%). --- compiler/utils/OrdList.lhs | 22 ++++++++++++---------- 1 file changed, 12 insertions(+), 10 deletions(-) diff --git a/compiler/utils/OrdList.lhs b/compiler/utils/OrdList.lhs index 7e797e0..328a5c1 100644 --- a/compiler/utils/OrdList.lhs +++ b/compiler/utils/OrdList.lhs @@ -20,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 @@ -36,14 +37,14 @@ 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 @@ -77,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} -- 1.7.10.4