new Bag type: :: Bag x = Pair (Bag x) (Bag x) | Single x | Empty

using this for accumulators is more elegant than using lists


git-svn-id: https://svn.cs.ru.nl/repos/clean-compiler/trunk@216 1f8540f1-abd5-4d5b-9d24-4c5ce8603e2d

1 files changed, 30 insertions, 0 deletions

diff --git a/frontend/utilities.icl b/frontend/utilities.icl
index c721d71..b7cb0d5 100644
--- a/frontend/utilities.icl
+++ b/frontend/utilities.icl
@@ -222,3 +222,33 @@ zip2Append [] [] tail
 zip2Append [x : xs] [y : ys] tail
 	= [(x,y) : zip2Append xs ys tail]
 */
+
+:: Bag x = Empty | Single !x | Pair !(Bag x) !(Bag x)
+
+uniqueBagToList :: !*(Bag x) -> [x] // exploits reuse of unique nodes (if compiled with that option)
+uniqueBagToList bag
+	= accumulate_elements bag []
+  where
+	accumulate_elements :: !*(Bag x) [x] -> [x]
+	accumulate_elements Empty accu
+		= accu
+	accumulate_elements (Single element) accu
+		= [element : accu]
+	accumulate_elements (Pair bag1 bag2) accu
+		= accumulate_elements bag1 (accumulate_elements bag2 accu)
+		
+bagToList :: !(Bag x) -> [x]
+bagToList bag
+	= accumulate_elements bag []
+  where
+	accumulate_elements :: !(Bag x) [x] -> [x]
+	accumulate_elements Empty accu
+		= accu
+	accumulate_elements (Single element) accu
+		= [element : accu]
+	accumulate_elements (Pair bag1 bag2) accu
+		= accumulate_elements bag1 (accumulate_elements bag2 accu)
+		
+isEmptyBag :: !(Bag x) -> Bool
+isEmptyBag Empty = True
+isEmptyBag _ = False