From 0065d5ab628975892cea1ec7303f968c3338cbe1 Mon Sep 17 00:00:00 2001
From: Simon Marlow <simonmar@microsoft.com>
Date: Fri, 7 Apr 2006 02:05:11 +0000
Subject: Reorganisation of the source tree Most of the other users of the
 fptools build system have migrated to Cabal, and with the move to darcs we
 can now flatten the source tree without losing history, so here goes.

The main change is that the ghc/ subdir is gone, and most of what it
contained is now at the top level.  The build system now makes no
pretense at being multi-project, it is just the GHC build system.

No doubt this will break many things, and there will be a period of
instability while we fix the dependencies.  A straightforward build
should work, but I haven't yet fixed binary/source distributions.
Changes to the Building Guide will follow, too.
---
 compiler/utils/OrdList.lhs | 83 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)
 create mode 100644 compiler/utils/OrdList.lhs

(limited to 'compiler/utils/OrdList.lhs')

diff --git a/compiler/utils/OrdList.lhs b/compiler/utils/OrdList.lhs
new file mode 100644
index 0000000000..7f22b38e49
--- /dev/null
+++ b/compiler/utils/OrdList.lhs
@@ -0,0 +1,83 @@
+%
+% (c) The AQUA Project, Glasgow University, 1993-1998
+%
+
+This is useful, general stuff for the Native Code Generator.
+
+Provide trees (of instructions), so that lists of instructions
+can be appended in linear time.
+
+\begin{code}
+module OrdList (
+	OrdList, 
+        nilOL, isNilOL, unitOL, appOL, consOL, snocOL, concatOL,
+        fromOL, toOL, foldrOL, foldlOL
+) where
+
+infixl 5  `appOL`
+infixl 5  `snocOL`
+infixr 5  `consOL`
+
+data OrdList a
+  = Many [a]
+  | Two (OrdList a) (OrdList a)
+  | One  a
+  | None
+
+nilOL    :: OrdList a
+isNilOL  :: OrdList a -> Bool
+
+unitOL   :: a           -> OrdList a
+snocOL   :: OrdList a   -> a         -> OrdList a
+consOL   :: a           -> OrdList a -> OrdList a
+appOL    :: OrdList a   -> OrdList a -> OrdList a
+concatOL :: [OrdList a] -> OrdList a
+
+nilOL        = None
+unitOL as    = One as
+snocOL as b  = Two as (One b)
+consOL a  bs = Two (One a) bs
+concatOL aas = foldr Two None aas
+
+isNilOL None        = True
+isNilOL (One _)     = False
+isNilOL (Two as bs) = isNilOL as && isNilOL bs
+isNilOL (Many xs)   = null xs
+
+appOL None bs   = bs
+appOL as   None = as
+appOL as   bs   = Two as bs
+
+mapOL :: (a -> b) -> OrdList a -> OrdList b
+mapOL f None = None
+mapOL f (One x) = One (f x)
+mapOL f (Two x y) = Two (mapOL f x) (mapOL f y)
+mapOL f (Many xs) = Many (map f xs)
+
+instance Functor OrdList where
+  fmap = mapOL
+
+foldrOL :: (a->b->b) -> b -> OrdList a -> b
+foldrOL k z None        = z
+foldrOL k z (One x)     = k x z
+foldrOL k z (Two b1 b2) = foldrOL k (foldrOL k z b2) b1
+foldrOL k z (Many xs)   = foldr k z xs
+
+foldlOL :: (b->a->b) -> b -> OrdList a -> b
+foldlOL k z None        = z
+foldlOL k z (One x)     = k z x
+foldlOL k z (Two b1 b2) = foldlOL k (foldlOL k z b1) b2
+foldlOL k z (Many xs)   = foldl k z xs
+
+fromOL :: OrdList a -> [a]
+fromOL ol 
+   = flat ol []
+     where
+        flat None      rest = rest
+        flat (One x)   rest = x:rest
+        flat (Two a b) rest = flat a (flat b rest)
+	flat (Many xs) rest = xs ++ rest
+
+toOL :: [a] -> OrdList a
+toOL xs = Many xs
+\end{code}
-- 
cgit v1.2.1