2 % (c) The University of Glasgow 2006
3 % (c) The AQUA Project, Glasgow University, 1993-1998
6 This is useful, general stuff for the Native Code Generator.
8 Provide trees (of instructions), so that lists of instructions
9 can be appended in linear time.
14 nilOL, isNilOL, unitOL, appOL, consOL, snocOL, concatOL,
15 mapOL, fromOL, toOL, foldrOL, foldlOL
23 = Many [a] -- Invariant: non-empty
24 | Two (OrdList a) -- Invariant: non-empty
25 (OrdList a) -- Invariant: non-empty
30 isNilOL :: OrdList a -> Bool
32 unitOL :: a -> OrdList a
33 snocOL :: OrdList a -> a -> OrdList a
34 consOL :: a -> OrdList a -> OrdList a
35 appOL :: OrdList a -> OrdList a -> OrdList a
36 concatOL :: [OrdList a] -> OrdList a
41 snocOL as b = Two as (One b)
43 consOL a bs = Two (One a) bs
44 concatOL aas = foldr appOL None aas
51 appOL as bs = Two as bs
53 mapOL :: (a -> b) -> OrdList a -> OrdList b
55 mapOL f (One x) = One (f x)
56 mapOL f (Two x y) = Two (mapOL f x) (mapOL f y)
57 mapOL f (Many xs) = Many (map f xs)
59 instance Functor OrdList where
62 foldrOL :: (a->b->b) -> b -> OrdList a -> b
64 foldrOL k z (One x) = k x z
65 foldrOL k z (Two b1 b2) = foldrOL k (foldrOL k z b2) b1
66 foldrOL k z (Many xs) = foldr k z xs
68 foldlOL :: (b->a->b) -> b -> OrdList a -> b
70 foldlOL k z (One x) = k z x
71 foldlOL k z (Two b1 b2) = foldlOL k (foldlOL k z b1) b2
72 foldlOL k z (Many xs) = foldl k z xs
74 fromOL :: OrdList a -> [a]
79 flat (One x) rest = x:rest
80 flat (Two a b) rest = flat a (flat b rest)
81 flat (Many xs) rest = xs ++ rest
83 toOL :: [a] -> OrdList a