如何在Haskell中使用部分顺序对列表进行排序？

Question

我有一个使用语句块的程序EDSL.

尽管语句之间可能存在依赖关系,但这些语句没有按特定顺序添加到块中.

但是,在编译EDSL期间,我需要确保语句按依赖顺序排序,例如

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我还没弄清楚如何使用它或它是否适用.

下面是一个包含绑定和非绑定语句的最小示例.非biniding语句的顺序很重要,并且它们必须保持原始顺序(即排序需要与没有依赖关系的语句保持稳定).

我希望有一个简单的解决方案,而不使用完整的依赖图...

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既不是订购也不是部分订购.特别是,它不是传递性的,这就是使用它进行排序的尝试失败的原因.

您正在寻找的是拓扑排序.你有一个顶点(语句)图形,它们之间有它们的边缘(它们的依赖关系),你想确保排序与边缘匹配.

我将只关注声明,因为非绑定语句很容易(我们只需要将列表拆分为两个,对声明进行排序并再次连接).

拓扑排序已在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实例.您可能希望检查SCCs是否为循环(循环将是语言编译错误),如果没有,则提取排序的序列.