हास्केल में आंशिक क्रम का उपयोग करके सूची को कैसे क्रमबद्ध करें?

Question

मेरे पास एक प्रक्रियात्मक ईडीएसएल है जो बयानों के ब्लॉक का उपयोग करता है।

ये बयान किसी विशेष क्रम में ब्लॉक में जोड़े गए हैं हालांकि बयान के बीच निर्भरता हो सकती है।

ईडीएसएल के संकलन के दौरान, मुझे यह सुनिश्चित करना होगा कि निर्भरता के क्रम में बयान का आदेश दिया गया हो, उदा।

B := A 
C := B 
E := D 

के बाद से नहीं सभी बयानों निर्भरता है वहाँ कोई कुल आदेश है (जैसे E := D ऊपर स्वतंत्र है और कहीं भी रखा जा सकता है)। कोई चक्रीय निर्भरता नहीं है इसलिए सूची क्रम संभव होना चाहिए।

मैं Data.List.sortBy का उपयोग करने और Ordering जो EQ वापसी होगी मतलब है कि बयान कोई निर्भरता है परिभाषित करने के लिए एक समाधान को हैक करने की कोशिश की है। यह कुछ उदाहरणों के लिए काम करता था लेकिन सामान्य मामले में नहीं, उदाहरण के लिए निम्नलिखित आदेश देने कुछ नहीं किया:

C := B       B := A 
D := C = should produce => C := B 
B := A       D := C 

इसका कारण यह है डिफ़ॉल्ट सॉर्ट प्रविष्टि प्रकार और केवल यकीन डाला आइटम छोटे या अगले के बराबर है बनाता है।

मैं एक Poset कार्यान्वयन के लिए इन्टरनेट की खोज की है, लेकिन कुछ भी लागू नहीं पाया है:

altfloat:Data.Poset को परिभाषित करता है Ordering = LT | GT | EQ | NC (गैर तुलनीय के लिए NC) जो अच्छा है, लेकिन उपलब्ध कराई गई sort मान लिया गया NaN तरह गैर तुलनीय वस्तुओं और बस उन्हें दूर फेंकता है।

logfloat:Data.Number.PartialOrd उपरोक्त के समान है Maybe Ordering को छोड़कर और मुझे पैकेज में कहीं भी सॉर्टिंग फ़ंक्शन दिखाई नहीं देता।

Math.Combinatorics.Poset मुझे यह पता नहीं लगाया गया है कि इसका उपयोग कैसे किया जाए या यह लागू हो।

नीचे एक न्यूनतम उदाहरण है जिसमें दोनों बाध्यकारी और गैर बाध्यकारी बयान हैं। गैर-बिनडिंग स्टेटमेंट का आदेश मायने रखता है और उन्हें मूल ऑर्डर को बनाए रखना चाहिए (यानी सॉर्टिंग स्थिर w.r.t. स्टेटमेंट्स होना चाहिए जिन पर निर्भरता संबंध नहीं है)।

मुझे आशा है कि वहाँ एक पूर्ण विकसित निर्भरता ग्राफ का उपयोग किए बिना यह करने के लिए एक सरल उपाय है ...

module Stmts where 

import Data.List (sortBy) 

data Var = A | B | C | D | E | F | G | H deriving (Eq, Show) 
data Stmt = Var := Var 
      | Inc Var 
    deriving (Show) 

-- LHS variable 
binds :: Stmt -> Maybe Var 
binds (v := _) = Just v 
binds _  = Nothing 

-- RHS variables 
references :: Stmt -> [Var] 
references (_ := v) = [v] 
references (Inc v) = [v] 

order :: [Stmt] -> [Stmt] 
order = sortBy orderStmts 

orderStmts :: Stmt -> Stmt -> Ordering 
orderStmts s1 s2 = ord mbv1 mbv2 
where 
    ord Nothing Nothing = EQ -- No dep since they don't bind vars 
    ord (Just v1) Nothing = LT -- Binding statements have precedence 
    ord Nothing (Just v2) = GT -- ^^^ 
    ord (Just v1) (Just v2)  -- Both statements are binding: 
    | v1 `elem` refs2 = LT  -- * s2 depends on s1 
    | v2 `elem` refs1 = GT  -- * s1 depends on s2 
    | otherwise  = EQ  -- * neither 

    -- *Maybe* they bind variables 
    mbv1 = binds s1 
    mbv2 = binds s2 

    -- Variables they reference 
    refs1 = references s1 
    refs2 = references s2 

-- The following should return [B := A, C := B, D := C, Inc F, Inc G] 
test = order [Inc F, Inc G, C := B, D := C, B := A] 

Answer 1

आपके दृष्टिकोण के साथ समस्या यह है कि आपका orderStmts न तो एक आदेश है और न ही आंशिक क्रम है। विशेष रूप से, यह transitive नहीं है और यही कारण है कि सॉर्टिंग के लिए इसका उपयोग करने में प्रयास विफल हो जाते हैं।

जो आप खोज रहे हैं topological sorting है। आपके पास शिखर (कथन) का एक ग्राफ है जिसमें उनके बीच किनारों (उनकी निर्भरताएं) हैं और आप यह सुनिश्चित करना चाहते हैं कि ऑर्डरिंग किनारों से मेल खाती हो।

मैं केवल घोषणाओं पर ध्यान केंद्रित करूंगा, क्योंकि गैर बाध्यकारी बयान आसान हैं (हमें केवल सूची में विभाजित करने की आवश्यकता है, घोषणाओं को क्रमबद्ध करें और फिर से संयोजित करें)।

Topological छंटाई पहले से ही Data.Graph में कार्यान्वित किया जाता है, जो बहुत ही सरल कार्य करता है:

module Stmts where 

import Data.Graph 

data Var = A | B | C | D | E | F | G | H deriving (Eq, Ord, Show) 

data Decl = Var := Var 
    deriving (Show, Eq) 

data Stmt = Decl 
      | Inc Var 
    deriving (Show, Eq) 

sortDecls :: [Decl] -> [SCC Decl] 
sortDecls = stronglyConnComp . map triple 
    where 
    triple n@(x := y) = (n, x, [y]) 

-- The following should return [B := A, C := B, D := C] 
test = map flattenSCC . sortDecls $ [C := B, D := C, B := A] 

कॉलिंग flattenSCC केवल परीक्षण के लिए है, के रूप में SCC कोई Show उदाहरण है। आप शायद चक्रों के लिए SCC एस (एक चक्र एक भाषा संकलन त्रुटि होगी) की जांच करना चाहते हैं, और यदि कोई नहीं है, क्रमबद्ध अनुक्रम निकालें।

Answer 2

मैं अपने बयान समूहों जड़ों से बच्चों के लिए चल रहे हैं सॉर्ट करने के लिए एक ही रास्ता लगता है

import Data.List 

data Var = A | B | C | D | E | F | G | H deriving (Eq, Show) 
data Stmt = Var := Var deriving (Show) 

parent :: Stmt -> Var 
parent (_ := p) = p 

child :: Stmt -> Var 
child (c := _) = c 

steps :: [Stmt] -> [[Stmt]] 
steps st = step roots st 
    where step _ [] = [] 
     step r s = let (a, b) = partition (flip elem r . parent) s 
         (v, u) = partition (flip elem (map child b) . child) a 
        in if null u then error "Cycle!" 
           else u : step (r ++ (nub $ map child u)) (v ++ b) 

     roots = let cs = map child st 
        rs = nub $ filter (not . flip elem cs) (map parent st) 
       in if null rs then error "No roots!" 
           else rs 

main = mapM_ print $ steps [F := H, G := H, C := B, D := C, B := A] 

उत्पादन के साथ

[F := H,G := H,B := A] 
[C := B] 
[D := C] 

जब "प्रकार" समूह (नहीं बयान खत्म हो गया है)।

(इस कोड पर स्थिरता दी गई है, क्योंकि partition, map, ++, के माध्यम से परिवर्तनीय है ...)

(जोड़ा)

तुम सच में कुछ स्थिरता संपत्ति चाहते हैं (अपने बयान छँटाई) आप कुछ अन्य प्रतिबंध जोड़ने के लिए करना होगा ("स्थिरता" को परिभाषित करने)।

चलो दो "प्रकार" प्रत्यक्ष एल्गोरिदम

orderToFront :: [Stmt] -> [Stmt] 
orderToFront [] = [] 
orderToFront (s@(_ := p):xs) = let (l, r) = splitAtFirst ((==p).child) xs 
           in if null r then s: orderToFront xs 
              else head r: s: orderToFront (l ++ tail r) 

orderToBack' :: [Stmt] -> [Stmt] 
orderToBack' [] = [] 
orderToBack' (s@(c := _):xs) = let (l, r) = splitAtFirst ((==c).parent) xs 
           in if null r then s: orderToBack' xs 
              else orderToBack' (l ++ head r: s: tail r) 
orderToBack = reverse . orderToBack' 

splitAtFirst :: (a -> Bool) -> [a] -> ([a], [a]) 
splitAtFirst f xs = let rs = dropWhile (not.f) xs 
        in (take (length xs - length rs) xs, rs) 


main = do 

    let q = [F := H, C := B, D := C, G := F, B := A] 

    putStrLn "-- orderToFront" 
    mapM_ print $ orderToFront q 

    putStrLn "-- orderToBack" 
    mapM_ print $ orderToBack q 

एक ही इनपुट के साथ

(बस या वापस करने के लिए सामने बयान को पुन: क्रम), orderToFront उत्पादन orderToBack उत्पादन की तुलना में अलग है, लेकिन दोनों मान्य हैं

-- orderToFront 
F := H 
B := A 
C := B 
D := C 
G := F 
-- orderToBack 
B := A 
F := H 
G := F 
C := B 
D := C 

(केवल समानता संबंध के साथ आपका एल्गोरिदम ओ (एन^2) से कम नहीं हो सकता है, लेकिन यदि आप स्थिरता प्रतिबंध को परिभाषित करते हैं तो इसे कम किया जा सकता है)