From: Ian Lynagh <igloo@earth.li>
Date: Thu, 16 Aug 2007 02:15:14 +0000 (+0000)
Subject: Optimise Digraph.postOrd, used when finding strongly connected components
X-Git-Url: http://git.megacz.com/?p=ghc-hetmet.git;a=commitdiff_plain;h=0ee1d0fd7b5cae2857fe6632cbee5441c011bb99

Optimise Digraph.postOrd, used when finding strongly connected components
---

diff --git a/compiler/utils/Digraph.lhs b/compiler/utils/Digraph.lhs
index cde008a..c5c9b57 100644
--- a/compiler/utils/Digraph.lhs
+++ b/compiler/utils/Digraph.lhs
@@ -323,17 +323,17 @@ preArr bnds      = tabulate bnds . preorderF
 ------------------------------------------------------------
 
 \begin{code}
---postorder :: Tree a -> [a]
-postorder (Node a ts) = postorderF ts ++ [a]
+postorder :: Tree a -> [a] -> [a]
+postorder (Node a ts) = postorderF ts . (a :)
 
-postorderF   :: Forest a -> [a]
-postorderF ts = concat (map postorder ts)
+postorderF   :: Forest a -> [a] -> [a]
+postorderF ts = foldr (.) id $ map postorder ts
 
-postOrd      :: Graph -> [Vertex]
-postOrd       = postorderF . dff
+postOrd :: Graph -> [Vertex]
+postOrd g = postorderF (dff g) []
 
-topSort      :: Graph -> [Vertex]
-topSort       = reverse . postOrd
+topSort :: Graph -> [Vertex]
+topSort = reverse . postOrd
 \end{code}