Rosetta Code

Topological sort: Difference between revisions

Page Discussion

Topological sort (view source)

Revision as of 22:25, 16 October 2018

85 bytes removed ,  5 years ago
→‎{{header|Haskell}}: Pruned and specified imports, applied hlint and hindent, added type signature.
m (→‎{{header|REXX}}: changed case of spelling,)
(→‎{{header|Haskell}}: Pruned and specified imports, applied hlint and hindent, added type signature.)
Line 2,441:
 
=={{header|Haskell}}==
<lang haskell>import Data.List ((\\), elemIndex, intersect, nub)
import DataControl.MaybeArrow ((***), first)
import Control.Arrow
import System.Random
import Control.Monad
 
combs 0 _ = [[]]
combs _ [] = []
combs k (x:xs) = map ((x :) (<$> combs (k - 1) xs) ++ combs k xs
 
depLibs :: [(String, String)]
depLibs =
depLibs = [("des_system_lib","std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee"),
[ ( "des_system_lib"
("dw01","ieee dw01 dware gtech"),
, "std synopsys std_cell_lib des_system_lib ("dw02","ieee dw02dw01 ramlib dwareieee"),
, ("dw03dw01", "stdieee synopsysdw01 dware dw03 dw02 dw01 ieee gtech"),
, ("dw04dw02", "dw04 ieee dw01dw02 dware gtech"),
, ("dw03", "std synopsys dware dw03 dw02 ("dw05","dw05dw01 ieee dwaregtech"),
, ("dw06dw04", "dw06dw04 ieee dw01 dware gtech"),
, ("dw07dw05", "dw05 ieee dware"),
, ("dwaredw06", "dw06 ieee dware"),
, ("gtechdw07", "ieee gtechdware"),
, ("ramlibdware", "stdieee ieeedware"),
, ("std_cell_libgtech", "ieee std_cell_libgtech"),
, ("synopsysramlib",[] "std ieee")]
, ("std_cell_lib", "ieee std_cell_lib")
 
, ("synopsys", [])
]
 
toposort :: [(String, String)] -> [String]
toposort xs
| (not . null) cycleDetect = error $ "Dependency cycle detected for libs " ++ show cycleDetect
error $ "Dependency cycle detected for libs " ++ show cycleDetect
| otherwise = foldl makePrecede [] dB
 
where
where dB = map ((\(x, y) -> (x, y \\ x)) . (return *** words)) <$> xs
 
makePrecede ts ([x], xs) = nub $ case elemIndex x ts of
nub $
Just i -> uncurry(++) $ first(++xs) $ splitAt i ts▼
case elemIndex x ts of
_ -> ts ++ xs ++ [x]▼
▲ Just i -> uncurry (++) $ first (++ xs) $ splitAt i ts
▲ _ -> ts ++ xs ++ [x]
cycleDetect =
cycleDetect = filter ((> 1) . length) $▼
$ map (\[(a, as), (b, bs)] -> (a `intersect` bs) ++ (b `intersect` as)) <$>▼
combs 2 dB
 
main :: IO ()
▲ cycleDetect = filter ((>1).length)
main = print $ toposort depLibs</lang>
▲ $ map (\[(a,as), (b,bs)] -> (a `intersect` bs) ++ (b `intersect`as))
$ combs 2 dB</lang>
{{out}}
<lang haskell>*Main> toposort depLibs
Hout
9,655

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/118325"