Haskell 中逻辑表达式的数据结构
A data structure for Logical Expressions in Haskell
我尝试创建一个用于处理逻辑表达式的数据结构。乍一看，逻辑表达式看起来像Trees，所以从树上凑起来似乎很合理：
data Property a = And (Property a) (Property a) |
Or (Property a) (Property a) |
Not (Property a) | Property a deriving (Show,Eq)
但这不是一个好主意，因为我的树的左右分支之间确实没有区别，因为 A && B == B && A
嗯，也许 List 更好？
data Property a = Empty | And a (Property a) | Or a (Property a) | Not a (Property a) deriving Show
但是在这种情况下，我无法真正形成一个'logic tree'，只能形成一个'logic list '。
所以我需要一个类似于Tree但没有左右"branching"的数据结构。
我们将遵循 Daniel Wagner 的出色建议并使用 "naive representation (your first one), plus a function that picks one of the famous normal forms"。我们将使用 algebraic normal form 有两个原因。主要原因是代数范式不需要枚举Property中变量类型的所有可能值。代数范式也相当简单。
代数范式
我们将使用不导出其构造函数的 newtype ANF a = ANF [[a]] 表示代数范式。每个内部列表都是其所有谓词的连词（and-ing）；如果内部列表为空，则它始终为真。外部列表是其所有谓词的异或运算；如果为空则为假。
module Logic (
ANF (getANF),
anf,
...
)
newtype ANF a = ANF {getANF :: [[a]]}
deriving (Eq, Ord, Show)
我们将努力使我们构建的任何 ANF 都是规范的。我们将构建 ANFs 以便内部列表始终排序且唯一。外部列表也将始终排序。如果外部列表中有两个（或偶数个）相同的项目，我们将把它们都删除。如果外部列表中有奇数个相同的项目，我们将删除其中一个以外的所有项目。
使用 Data.List.Ordered in the data-ordlist 包中的函数，我们可以将表示连词异或运算的列表列表清理成一个 ANF，对列表进行排序并删除重复项。
import qualified Data.List.Ordered as Ordered
anf :: Ord a => [[a]] -> ANF a
anf = ANF . nubPairs . map Ordered.nubSort
nubPairs :: Ord a => [a] -> [a]
nubPairs = removePairs . Ordered.sort
where
removePairs (x:y:zs)
| x == y = removePairs zs
| otherwise = x:removePairs (y:zs)
removePairs xs = xs
逻辑表达式组成一个boolean algebra, which is a bounded lattice with an additional distributive law and a complement (negation). Taking advantage of the existing BoundedLattice class in the lattices包，我们可以定义BooleanAlgebras
的class
import Algebra.Lattice
class (BoundedLattice a) => BooleanAlgebra a where
complement :: a -> a
-- Additional Laws:
-- a `join` complement a == top
-- a `meet` complement a == bottom
-- a `join` (b `meet` c) == (a `join` b) `meet` (a `join` c)
-- a `meet` (b `join` c) == (a `meet` b) `join` (a `meet` c)
每当 a 有一个 Ord 实例时，ANF a 就会形成一个 BooleanAlgebra，这样我们就可以保持 ANF 的规范形式。
布尔代数的meet是合乎逻辑的and。逻辑 and 分布在 xor 中。我们将利用内部列表已经排序的事实来快速将它们清楚地合并在一起。
instance (Ord a) => MeetSemiLattice (ANF a) where
ANF xs `meet` ANF ys = ANF (nubPairs [Ordered.union x y | x <- xs, y <- ys])
使用De Morgan's laws，join或逻辑or可以写成meet或逻辑and。
instance (Ord a) => JoinSemiLattice (ANF a) where
xs `join` ys = complement (complement xs `meet` complement ys)
格子的top永远为真
instance (Ord a) => BoundedMeetSemiLattice (ANF a) where
top = ANF [[]]
格子的bottom总是假的
instance (Ord a) => BoundedJoinSemiLattice (ANF a) where
bottom = ANF []
逻辑and和逻辑or满足晶格吸收定律，a join (a meet b) == a meet (a join b) == a.
instance (Ord a) => Lattice (ANF a)
instance (Ord a) => BoundedLattice (ANF a)
最后complement运算为取反，可以通过xor取真来完成
instance (Ord a) => BooleanAlgebra (ANF a) where
complement (ANF ([]:xs)) = ANF xs
complement (ANF xs) = ANF ([]:xs)
连同 Pointed 我们可以使用 BooleanAlgebra 来定义包含逻辑表达式的事物的 class，Logical.
import Data.Pointed
class Logical f where
toLogic :: (Pointed g, BooleanAlgebra (g a)) => f a -> g a
代数范式包含一个逻辑表达式。
xor :: BooleanAlgebra a => a -> a -> a
p `xor` q = (p `join` q) `meet` complement (p `meet` q)
instance Logical ANF where
toLogic = foldr xor bottom . map (foldr meet top . map point) . getANF
代数范式也是Pointed，因此可以转换为使用toLogic。
instance Pointed ANF where
point x = ANF [[x]]
toANF :: (Logical f, Ord a) => f a -> ANF a
toANF = toLogic
我们可以通过比较转换为规范代数范式时是否在结构上等价来测试Logical是否在逻辑上等价。
equivalent :: (Logical f, Logical g, Ord a) => f a -> g a -> Bool
equivalent a b = toANF a == toANF b
正在将 属性 转换为 ANF
逻辑表达式应该构成一个布尔代数，它是一个附加分配律和一个补（否定）的有界格。为了使 Property 更接近布尔代数，我们需要为格子的 top 和 bottom 边界添加两个元素。 top 始终是 True，而 bottom 始终是 False。对于始终为 True 的属性，我将调用这些 Trivial，对于始终为 False.
的属性，我将调用这些 Impossible
data Property a
= And (Property a) (Property a)
| Or (Property a) (Property a)
| Not (Property a)
| Property a
| Trivial
| Impossible
deriving (Eq, Ord, Read, Show)
Property 是 属性 的抽象语法树。它派生的 Eq 和 Ord 实例只是结构相等。
一个Property就是Logical，我们可以把它转换成任意PointedBooleanAlgebra.
instance Logical Property where
toLogic (And a b) = (toLogic a) `meet` (toLogic b)
toLogic (Or a b) = (toLogic a) `join` (toLogic b)
toLogic (Not a) = complement (toLogic a)
toLogic (Property a) = point a
toLogic Trivial = top
toLogic Impossible = bottom
使用上一节的 equivalent 和我们的 Logical 实例，我们可以检查某些示例的两个属性是否等价。
runExample :: (Ord a, Show a) => Property a -> Property a -> IO ()
runExample p q =
if p `equivalent` q
then putStrLn (show p ++ " == " ++ show q)
else putStrLn (show p ++ " /= " ++ show q)
main = do
runExample (point 'a' `meet` point 'b') (point 'b' `meet` point 'a')
runExample (point 'a' `meet` point 'b') (point 'b' `meet` point 'a' `meet` point 'a')
runExample (point 'a' `meet` point 'b') (point 'b' `meet` point 'a' `join` point 'a')
runExample (point 'a' `join` complement (point 'a')) (top)
runExample (point 'a' `meet` complement (point 'a')) (bottom)
这会产生以下输出。
And (Property 'a') (Property 'b') == And (Property 'b') (Property 'a')
And (Property 'a') (Property 'b') == And (And (Property 'b') (Property 'a')) (Pr
operty 'a')
And (Property 'a') (Property 'b') /= Or (And (Property 'b') (Property 'a')) (Pro
perty 'a')
Or (Property 'a') (Not (Property 'a')) == Trivial
And (Property 'a') (Not (Property 'a')) == Impossible
要按书面形式使用这些示例，我们还需要 Property 的 BooleanAlgebra 和 Pointed 个实例。 BooleanAlgebra定律的等价关系是等价解释而不是Property.
的结构等式
instance MeetSemiLattice (Property a) where
meet = And
instance BoundedMeetSemiLattice (Property a) where
top = Trivial
instance JoinSemiLattice (Property a) where
join = Or
instance BoundedJoinSemiLattice (Property a) where
bottom = Impossible
instance Lattice (Property a)
instance BoundedLattice (Property a)
instance BooleanAlgebra (Property a) where
complement = Not
instance Pointed Property where
point = Property
证明
每个布尔函数，因此每个有限 Property，在 ANF 中都有一个 唯一的 表示。 ANF 的 BooleanAlgebra 和 Pointed 实例证明了一切 Logical a，因此每个有限 Property a 和由 a 索引的布尔函数，都有一个ANF a 中的代表。设 k 为 a 的居民人数。 k 个布尔变量有 2^(2^k) 个可能的布尔函数。 ANF 的每个内部列表都是一组 a；有 2^k 个可能的 a 集合，因此有 2^k 个可能的内部列表。 ANF 的外部列表是一组内部列表；每个内部列表最多只能在外部列表中出现一次。有 2^(2^k) 个可能的 ANF a。由于每个布尔函数在 ANF 中都有一个表示，并且 ANF 的可能居民数量与布尔函数的数量一样多，因此每个布尔函数都有一个 唯一的 表示在 ANF.
免责声明
ANF的Ord实例是一个结构序，除了相等之外，与格结构引起的偏序无关。
代数范式可以比其输入指数大。 n 变量列表的析取大小为 .5*n*2^n。例如，length . getANF . foldr join bottom . map point $ ['a'..'g'] 是 127，foldr join bottom . map point $ ['a'..'g'] 包含总共 448 次出现的 7 个不同的变量。
如果想体现逻辑连接词and(&&)和or的结合性，使用数据结构这是关联的，如列表：
data Property a = And [Property a] | ...
如果您还想要交换性 (A && B == B && A)，请选择 Data.Set。
我记得这个方便的图表，如果您需要某些属性，可以使用哪些类型：
+-----------+-----------+----------+----------
|Associative|Commutative|Idempotent| type
+-----------+-----------+----------+----------
|(a+b)+c= | a+b=b+a | a+a=a |
| a+(b+c)| | |
+-----------+-----------+----------+----------
| no | no | no |binary trees
| no | yes | no | “mobiles”
| yes | no | no |lists (arrays)
| yes | yes | no |multisets (bags)
| yes | yes | yes |sets
+-----------+-----------+----------+----------
第 51 页，共 Guy Steele's Lecture。
我建议使用 SAT/SMT 求解器进行等价性检查。一般来说，这些类型的检查可能非常昂贵（NP 完全），并且任何类型的范式转换都可能导致表示形式呈指数级增长。 SAT/SMT 求解器具有处理此类问题的自定义算法，最好使用此类求解器。翻译 Property 的两个实例并询问它们在所有变量赋值下是否相同是微不足道的。 SBV 库 (https://hackage.haskell.org/package/sbv) can be used to do the translation from high-level Haskell. The answer to the following question has some details on how to go about doing that: SAT solving with haskell SBV library: how to generate a predicate from a parsed string?
我尝试创建一个用于处理逻辑表达式的数据结构。乍一看，逻辑表达式看起来像Trees，所以从树上凑起来似乎很合理：
data Property a = And (Property a) (Property a) |
Or (Property a) (Property a) |
Not (Property a) | Property a deriving (Show,Eq)
但这不是一个好主意，因为我的树的左右分支之间确实没有区别，因为 A && B == B && A
嗯，也许 List 更好？
data Property a = Empty | And a (Property a) | Or a (Property a) | Not a (Property a) deriving Show
但是在这种情况下，我无法真正形成一个'logic tree'，只能形成一个'logic list '。
所以我需要一个类似于Tree但没有左右"branching"的数据结构。
我们将遵循 Daniel Wagner 的出色建议并使用 "naive representation (your first one), plus a function that picks one of the famous normal forms"。我们将使用 algebraic normal form 有两个原因。主要原因是代数范式不需要枚举Property中变量类型的所有可能值。代数范式也相当简单。
代数范式
我们将使用不导出其构造函数的 newtype ANF a = ANF [[a]] 表示代数范式。每个内部列表都是其所有谓词的连词（and-ing）；如果内部列表为空，则它始终为真。外部列表是其所有谓词的异或运算；如果为空则为假。
module Logic (
ANF (getANF),
anf,
...
)
newtype ANF a = ANF {getANF :: [[a]]}
deriving (Eq, Ord, Show)
我们将努力使我们构建的任何 ANF 都是规范的。我们将构建 ANFs 以便内部列表始终排序且唯一。外部列表也将始终排序。如果外部列表中有两个（或偶数个）相同的项目，我们将把它们都删除。如果外部列表中有奇数个相同的项目，我们将删除其中一个以外的所有项目。
使用 Data.List.Ordered in the data-ordlist 包中的函数，我们可以将表示连词异或运算的列表列表清理成一个 ANF，对列表进行排序并删除重复项。
import qualified Data.List.Ordered as Ordered
anf :: Ord a => [[a]] -> ANF a
anf = ANF . nubPairs . map Ordered.nubSort
nubPairs :: Ord a => [a] -> [a]
nubPairs = removePairs . Ordered.sort
where
removePairs (x:y:zs)
| x == y = removePairs zs
| otherwise = x:removePairs (y:zs)
removePairs xs = xs
逻辑表达式组成一个boolean algebra, which is a bounded lattice with an additional distributive law and a complement (negation). Taking advantage of the existing BoundedLattice class in the lattices包，我们可以定义BooleanAlgebras
import Algebra.Lattice
class (BoundedLattice a) => BooleanAlgebra a where
complement :: a -> a
-- Additional Laws:
-- a `join` complement a == top
-- a `meet` complement a == bottom
-- a `join` (b `meet` c) == (a `join` b) `meet` (a `join` c)
-- a `meet` (b `join` c) == (a `meet` b) `join` (a `meet` c)
a 有一个 Ord 实例时，ANF a 就会形成一个 BooleanAlgebra，这样我们就可以保持 ANF 的规范形式。
布尔代数的meet是合乎逻辑的and。逻辑 and 分布在 xor 中。我们将利用内部列表已经排序的事实来快速将它们清楚地合并在一起。
instance (Ord a) => MeetSemiLattice (ANF a) where
ANF xs `meet` ANF ys = ANF (nubPairs [Ordered.union x y | x <- xs, y <- ys])
使用De Morgan's laws，join或逻辑or可以写成meet或逻辑and。
instance (Ord a) => JoinSemiLattice (ANF a) where
xs `join` ys = complement (complement xs `meet` complement ys)
格子的top永远为真
instance (Ord a) => BoundedMeetSemiLattice (ANF a) where
top = ANF [[]]
格子的bottom总是假的
instance (Ord a) => BoundedJoinSemiLattice (ANF a) where
bottom = ANF []
逻辑and和逻辑or满足晶格吸收定律，a join (a meet b) == a meet (a join b) == a.
instance (Ord a) => Lattice (ANF a)
instance (Ord a) => BoundedLattice (ANF a)
最后complement运算为取反，可以通过xor取真来完成
instance (Ord a) => BooleanAlgebra (ANF a) where
complement (ANF ([]:xs)) = ANF xs
complement (ANF xs) = ANF ([]:xs)
连同 Pointed 我们可以使用 BooleanAlgebra 来定义包含逻辑表达式的事物的 class，Logical.
import Data.Pointed
class Logical f where
toLogic :: (Pointed g, BooleanAlgebra (g a)) => f a -> g a
代数范式包含一个逻辑表达式。
xor :: BooleanAlgebra a => a -> a -> a
p `xor` q = (p `join` q) `meet` complement (p `meet` q)
instance Logical ANF where
toLogic = foldr xor bottom . map (foldr meet top . map point) . getANF
代数范式也是Pointed，因此可以转换为使用toLogic。
instance Pointed ANF where
point x = ANF [[x]]
toANF :: (Logical f, Ord a) => f a -> ANF a
toANF = toLogic
我们可以通过比较转换为规范代数范式时是否在结构上等价来测试Logical是否在逻辑上等价。
equivalent :: (Logical f, Logical g, Ord a) => f a -> g a -> Bool
equivalent a b = toANF a == toANF b
正在将 属性 转换为 ANF
逻辑表达式应该构成一个布尔代数，它是一个附加分配律和一个补（否定）的有界格。为了使 Property 更接近布尔代数，我们需要为格子的 top 和 bottom 边界添加两个元素。 top 始终是 True，而 bottom 始终是 False。对于始终为 True 的属性，我将调用这些 Trivial，对于始终为 False.
Impossible
data Property a
= And (Property a) (Property a)
| Or (Property a) (Property a)
| Not (Property a)
| Property a
| Trivial
| Impossible
deriving (Eq, Ord, Read, Show)
Property 是 属性 的抽象语法树。它派生的 Eq 和 Ord 实例只是结构相等。
一个Property就是Logical，我们可以把它转换成任意PointedBooleanAlgebra.
instance Logical Property where
toLogic (And a b) = (toLogic a) `meet` (toLogic b)
toLogic (Or a b) = (toLogic a) `join` (toLogic b)
toLogic (Not a) = complement (toLogic a)
toLogic (Property a) = point a
toLogic Trivial = top
toLogic Impossible = bottom
使用上一节的 equivalent 和我们的 Logical 实例，我们可以检查某些示例的两个属性是否等价。
runExample :: (Ord a, Show a) => Property a -> Property a -> IO ()
runExample p q =
if p `equivalent` q
then putStrLn (show p ++ " == " ++ show q)
else putStrLn (show p ++ " /= " ++ show q)
main = do
runExample (point 'a' `meet` point 'b') (point 'b' `meet` point 'a')
runExample (point 'a' `meet` point 'b') (point 'b' `meet` point 'a' `meet` point 'a')
runExample (point 'a' `meet` point 'b') (point 'b' `meet` point 'a' `join` point 'a')
runExample (point 'a' `join` complement (point 'a')) (top)
runExample (point 'a' `meet` complement (point 'a')) (bottom)
这会产生以下输出。
And (Property 'a') (Property 'b') == And (Property 'b') (Property 'a')
And (Property 'a') (Property 'b') == And (And (Property 'b') (Property 'a')) (Pr
operty 'a')
And (Property 'a') (Property 'b') /= Or (And (Property 'b') (Property 'a')) (Pro
perty 'a')
Or (Property 'a') (Not (Property 'a')) == Trivial
And (Property 'a') (Not (Property 'a')) == Impossible
要按书面形式使用这些示例，我们还需要 Property 的 BooleanAlgebra 和 Pointed 个实例。 BooleanAlgebra定律的等价关系是等价解释而不是Property.
instance MeetSemiLattice (Property a) where
meet = And
instance BoundedMeetSemiLattice (Property a) where
top = Trivial
instance JoinSemiLattice (Property a) where
join = Or
instance BoundedJoinSemiLattice (Property a) where
bottom = Impossible
instance Lattice (Property a)
instance BoundedLattice (Property a)
instance BooleanAlgebra (Property a) where
complement = Not
instance Pointed Property where
point = Property
证明
每个布尔函数，因此每个有限 Property，在 ANF 中都有一个 唯一的 表示。 ANF 的 BooleanAlgebra 和 Pointed 实例证明了一切 Logical a，因此每个有限 Property a 和由 a 索引的布尔函数，都有一个ANF a 中的代表。设 k 为 a 的居民人数。 k 个布尔变量有 2^(2^k) 个可能的布尔函数。 ANF 的每个内部列表都是一组 a；有 2^k 个可能的 a 集合，因此有 2^k 个可能的内部列表。 ANF 的外部列表是一组内部列表；每个内部列表最多只能在外部列表中出现一次。有 2^(2^k) 个可能的 ANF a。由于每个布尔函数在 ANF 中都有一个表示，并且 ANF 的可能居民数量与布尔函数的数量一样多，因此每个布尔函数都有一个 唯一的 表示在 ANF.
免责声明
ANF的Ord实例是一个结构序，除了相等之外，与格结构引起的偏序无关。
代数范式可以比其输入指数大。 n 变量列表的析取大小为 .5*n*2^n。例如，length . getANF . foldr join bottom . map point $ ['a'..'g'] 是 127，foldr join bottom . map point $ ['a'..'g'] 包含总共 448 次出现的 7 个不同的变量。
如果想体现逻辑连接词and(&&)和or的结合性，使用数据结构这是关联的，如列表：
data Property a = And [Property a] | ...
如果您还想要交换性 (A && B == B && A)，请选择 Data.Set。
我记得这个方便的图表，如果您需要某些属性，可以使用哪些类型：
+-----------+-----------+----------+----------
|Associative|Commutative|Idempotent| type
+-----------+-----------+----------+----------
|(a+b)+c= | a+b=b+a | a+a=a |
| a+(b+c)| | |
+-----------+-----------+----------+----------
| no | no | no |binary trees
| no | yes | no | “mobiles”
| yes | no | no |lists (arrays)
| yes | yes | no |multisets (bags)
| yes | yes | yes |sets
+-----------+-----------+----------+----------
第 51 页，共 Guy Steele's Lecture。
我建议使用 SAT/SMT 求解器进行等价性检查。一般来说，这些类型的检查可能非常昂贵（NP 完全），并且任何类型的范式转换都可能导致表示形式呈指数级增长。 SAT/SMT 求解器具有处理此类问题的自定义算法，最好使用此类求解器。翻译 Property 的两个实例并询问它们在所有变量赋值下是否相同是微不足道的。 SBV 库 (https://hackage.haskell.org/package/sbv) can be used to do the translation from high-level Haskell. The answer to the following question has some details on how to go about doing that: SAT solving with haskell SBV library: how to generate a predicate from a parsed string?