%
-% (c) The GRASP/AQUA Project, Glasgow University, 1992-1996
+% (c) The GRASP/AQUA Project, Glasgow University, 1992-1998
%
\section[Bags]{@Bag@: an unordered collection with duplicates}
\begin{code}
-#include "HsVersions.h"
-
module Bag (
Bag, -- abstract type
emptyBag, unitBag, unionBags, unionManyBags,
- mapBag, -- UNUSED: elemBag,
- filterBag, partitionBag, concatBag, foldBag,
+ mapBag,
+ elemBag,
+ filterBag, partitionBag, concatBag, foldBag, foldrBag, foldlBag,
isEmptyBag, consBag, snocBag,
listToBag, bagToList
) where
-#ifdef COMPILING_GHC
-IMP_Ubiq(){-uitous-}
-IMPORT_1_3(List(partition))
+#include "HsVersions.h"
+
+import Outputable
+import List ( partition )
+\end{code}
-import Outputable ( interpp'SP )
-import Pretty
-#endif
+\begin{code}
data Bag a
= EmptyBag
| UnitBag a
emptyBag = EmptyBag
unitBag = UnitBag
-{- UNUSED:
elemBag :: Eq a => a -> Bag a -> Bool
elemBag x EmptyBag = False
elemBag x (TwoBags b1 b2) = x `elemBag` b1 || x `elemBag` b2
elemBag x (ListBag ys) = any (x ==) ys
elemBag x (ListOfBags bs) = any (x `elemBag`) bs
--}
unionManyBags [] = EmptyBag
unionManyBags xs = ListOfBags xs
unionBags b1 b2 = TwoBags b1 b2
consBag :: a -> Bag a -> Bag a
-consBag elt bag = (unitBag elt) `unionBags` bag
snocBag :: Bag a -> a -> Bag a
+
+consBag elt bag = (unitBag elt) `unionBags` bag
snocBag bag elt = bag `unionBags` (unitBag elt)
isEmptyBag EmptyBag = True
foldBag t u e (ListBag xs) = foldr (t.u) e xs
foldBag t u e (ListOfBags bs) = foldr (\b r -> foldBag t u r b) e bs
+foldrBag :: (a -> r -> r) -> r
+ -> Bag a
+ -> r
+
+foldrBag k z EmptyBag = z
+foldrBag k z (UnitBag x) = k x z
+foldrBag k z (TwoBags b1 b2) = foldrBag k (foldrBag k z b2) b1
+foldrBag k z (ListBag xs) = foldr k z xs
+foldrBag k z (ListOfBags bs) = foldr (\b r -> foldrBag k r b) z bs
+
+foldlBag :: (r -> a -> r) -> r
+ -> Bag a
+ -> r
+
+foldlBag k z EmptyBag = z
+foldlBag k z (UnitBag x) = k z x
+foldlBag k z (TwoBags b1 b2) = foldlBag k (foldlBag k z b1) b2
+foldlBag k z (ListBag xs) = foldl k z xs
+foldlBag k z (ListOfBags bs) = foldl (\r b -> foldlBag k r b) z bs
+
mapBag :: (a -> b) -> Bag a -> Bag b
mapBag f EmptyBag = EmptyBag
listToBag vs = ListBag vs
bagToList :: Bag a -> [a]
-bagToList EmptyBag = []
-bagToList (ListBag vs) = vs
-bagToList b = bagToList_append b []
-
- -- (bagToList_append b xs) flattens b and puts xs on the end.
- -- (not exported)
-bagToList_append EmptyBag xs = xs
-bagToList_append (UnitBag x) xs = x:xs
-bagToList_append (TwoBags b1 b2) xs = bagToList_append b1 (bagToList_append b2 xs)
-bagToList_append (ListBag xx) xs = xx++xs
-bagToList_append (ListOfBags bs) xs = foldr bagToList_append xs bs
+bagToList b = foldrBag (:) [] b
\end{code}
\begin{code}
-#ifdef COMPILING_GHC
-
instance (Outputable a) => Outputable (Bag a) where
- ppr sty EmptyBag = ppStr "emptyBag"
- ppr sty (UnitBag a) = ppr sty a
- ppr sty (TwoBags b1 b2) = ppCat [ppr sty b1, pp'SP, ppr sty b2]
- ppr sty (ListBag as) = interpp'SP sty as
- ppr sty (ListOfBags bs) = ppCat [ppLbrack, interpp'SP sty bs, ppRbrack]
+ ppr EmptyBag = ptext SLIT("emptyBag")
+ ppr (UnitBag a) = ppr a
+ ppr (TwoBags b1 b2) = hsep [ppr b1 <> comma, ppr b2]
+ ppr (ListBag as) = interpp'SP as
+ ppr (ListOfBags bs) = brackets (interpp'SP bs)
-#endif {- COMPILING_GHC -}
\end{code}