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

, lastOL

,
15 mapOL

, fromOL

, toOL

, foldrOL

, foldlOL

22 import Data

.Semigroup

( Semigroup

)
23 import qualified Data

.Semigroup

as Semigroup

32 | Many

[a

] -- Invariant: non-empty
35 | Two

(OrdList a

) -- Invariant: non-empty
36 (OrdList a

) -- Invariant: non-empty
38 instance Outputable a

=> Outputable

(OrdList a

) where
39 ppr ol

= ppr

(fromOL ol

) -- Convert to list and print that
41 instance Semigroup

(OrdList a

) where
44 instance Monoid

(OrdList a

) where
46 mappend

= (Semigroup

.<>)
49 instance Functor OrdList

where
52 instance Foldable OrdList

where
55 instance Traversable OrdList

where
56 traverse f xs

= toOL

<$> traverse f

(fromOL xs

)
59 isNilOL

:: OrdList a

-> Bool
61 unitOL

:: a

-> OrdList a

62 snocOL

:: OrdList a

-> a

-> OrdList a

63 consOL

:: a

-> OrdList a

-> OrdList a

64 appOL

:: OrdList a

-> OrdList a

-> OrdList a

65 concatOL

:: [OrdList a

] -> OrdList a

66 lastOL

:: OrdList a

-> a

70 snocOL

as b

= Snoc

as b

71 consOL a bs

= Cons a bs

72 concatOL aas

= foldr appOL None aas

74 lastOL None

= panic

"lastOL"
76 lastOL

(Many

as) = last as
77 lastOL

(Cons _

as) = lastOL

as
79 lastOL

(Two _

as) = lastOL

as
86 One a `appOL` b

= Cons a b

87 a `appOL` One b

= Snoc a b

90 fromOL

:: OrdList a

-> [a

]
92 where go None acc

= acc

93 go

(One a

) acc

= a

: acc

94 go

(Cons a b

) acc

= a

: go b acc

95 go

(Snoc a b

) acc

= go a

(b

:acc

)
96 go

(Two a b

) acc

= go a

(go b acc

)
97 go

(Many xs

) acc

= xs

++ acc

99 mapOL

:: (a

-> b

) -> OrdList a

-> OrdList b

101 mapOL f

(One x

) = One

(f x

)
102 mapOL f

(Cons x xs

) = Cons

(f x

) (mapOL f xs

)
103 mapOL f

(Snoc xs x

) = Snoc

(mapOL f xs

) (f x

)
104 mapOL f

(Two x y

) = Two

(mapOL f x

) (mapOL f y

)
105 mapOL f

(Many xs

) = Many

(map f xs

)
107 foldrOL

:: (a

->b

->b

) -> b

-> OrdList a

-> b

109 foldrOL k z

(One x

) = k x z

110 foldrOL k z

(Cons x xs

) = k x

(foldrOL k z xs

)
111 foldrOL k z

(Snoc xs x

) = foldrOL k

(k x z

) xs

112 foldrOL k z

(Two b1 b2

) = foldrOL k

(foldrOL k z b2

) b1

113 foldrOL k z

(Many xs

) = foldr k z xs

115 foldlOL

:: (b

->a

->b

) -> b

-> OrdList a

-> b

117 foldlOL k z

(One x

) = k z x

118 foldlOL k z

(Cons x xs

) = foldlOL k

(k z x

) xs

119 foldlOL k z

(Snoc xs x

) = k

(foldlOL k z xs

) x

120 foldlOL k z

(Two b1 b2

) = foldlOL k

(foldlOL k z b1

) b2

121 foldlOL k z

(Many xs

) = foldl k z xs

123 toOL

:: [a

] -> OrdList a