作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
如何在 haskell 中对我将称之为“异构图”的内容进行建模,以便可以在编译时验证图的类型正确性?
为此,异构图是一组节点,每个节点都有一个特定的类型标签,以及一组边,每个节点都有一个源类型标签和一个目的地类型标签。
我们希望静态地确保,当一条边添加到图中时,该边的源类型标签与源节点的类型标签匹配,并且该边的目标类型标签与目标节点的类型标签匹配。但我们不希望以微不足道的方式做到这一点(通过强制整个图只包含具有一个特定类型标签的节点)。
最佳答案
我不确定我将如何在编译时强制执行此操作——我认为它要求你的图形完全静态?——但在运行时使用 Typeable
强制执行相对简单。 .这是一个草图,它会是什么样子。首先,我将从输入 Node
开始和 Edge
类型:
data Node a = Node a
data Edge a b = Edge !Int !Int
{-# LANGUAGE ExistentialQuantification #-}
import Data.Typeable
data SomeNode
= forall a. (Typeable a)
=> SomeNode (Node a)
data SomeEdge
= forall a b. (Typeable a, Typeable b)
=> SomeEdge (Edge a b)
import Data.IntMap (IntMap)
-- Not a great representation, but simple for illustration.
data Graph = Graph !(IntMap SomeNode) [SomeEdge]
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TypeApplications #-}
import qualified Data.IntMap as IntMap
addNode
:: forall a. (Typeable a)
=> Int -> a -> Graph -> Maybe Graph
addNode i x (Graph ns es) = case IntMap.lookup i ns of
-- If a node already exists at a given index:
Just (SomeNode (existing :: Node e)) -> case eqT @e @a of
-- Type-preserving replacement is allowed, but…
Just Refl -> Just $ Graph ns' es
-- …*type-changing* replacement is *not* allowed,
-- since it could invalidate existing edges.
Nothing -> Nothing
-- Insertion is of course allowed.
Nothing -> Just $ Graph ns' es
where
ns' = IntMap.insert i (SomeNode (Node x)) ns
-- To add an edge:
addEdge
:: forall a b. (Typeable a, Typeable b)
=> Edge a b -> Graph -> Maybe Graph
addEdge e@(Edge f t) (Graph ns es) = do
-- The ‘from’ node must exist…
SomeNode (fn :: Node tfn) <- IntMap.lookup f ns
-- …and have the correct type; and
Refl <- eqT @a @tfn
-- The ‘to’ node must exist…
SomeNode (tn :: Node ttn) <- IntMap.lookup t ns
-- …and have the correct type.
Refl <- eqT @b @ttn
pure $ Graph ns $ SomeEdge e : es
pure (Graph mempty mempty)
>>= addNode 0 (1 :: Int)
>>= addNode 1 ('x' :: Char)
>>= addEdge (Edge 0 1 :: Edge Int Char)
Int
/
Char
在
Edge Int Char
到无效类型,或
0
/
1
到无效索引,将失败并返回
Nothing
.
关于haskell - 在 Haskell 中建模异构图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50072210/
我是一名优秀的程序员,十分优秀!