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%).
infixr 5 `consOL`
data OrdList a
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
nilOL = None
unitOL as = One as
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 None bs = bs
appOL as None = as
flat None rest = rest
flat (One x) rest = x:rest
flat (Two a b) rest = flat a (flat b rest)
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 xs = Many xs
\end{code}
toOL xs = Many xs
\end{code}