ghc/compiler/utils/OrdList.lhs

   1 %
   2 % (c) The AQUA Project, Glasgow University, 1993-1998
   3 %
   4
   5 This is useful, general stuff for the Native Code Generator.
   6
   7 Provide trees (of instructions), so that lists of instructions
   8 can be appended in linear time.
   9
  10 \begin{code}
  11 module OrdList (
  12         OrdList,
  13         nilOL, isNilOL, unitOL, appOL, consOL, snocOL, concatOL,
  14         fromOL, toOL
  15 ) where
  16
  17 infixl 5  `appOL`
  18 infixl 5  `snocOL`
  19 infixr 5  `consOL`
  20
  21 data OrdList a
  22   = Many (OrdList a) (OrdList a)
  23   | One  a
  24   | None
  25
  26 nilOL    :: OrdList a
  27 isNilOL  :: OrdList a -> Bool
  28
  29 unitOL   :: a           -> OrdList a
  30 snocOL   :: OrdList a   -> a         -> OrdList a
  31 consOL   :: a           -> OrdList a -> OrdList a
  32 appOL    :: OrdList a   -> OrdList a -> OrdList a
  33 concatOL :: [OrdList a] -> OrdList a
  34
  35 nilOL        = None
  36 unitOL as    = One as
  37 snocOL as b  = Many as (One b)
  38 consOL a  bs = Many (One a) bs
  39 concatOL aas = foldr Many None aas
  40
  41 isNilOL None         = True
  42 isNilOL (One _)      = False
  43 isNilOL (Many as bs) = isNilOL as && isNilOL bs
  44
  45 appOL None bs   = bs
  46 appOL as   None = as
  47 appOL as   bs   = Many as bs
  48
  49 fromOL :: OrdList a -> [a]
  50 fromOL ol
  51    = flat ol []
  52      where
  53         flat None       rest = rest
  54         flat (One x)    rest = x:rest
  55         flat (Many a b) rest = flat a (flat b rest)
  56
  57 toOL :: [a] -> OrdList a
  58 toOL []     = None
  59 toOL (x:xs) = Many (One x) (toOL xs)
  60
  61 \end{code}