haskell - 如何在 Haskell 中创建格型数据结构?
问题描述
我正在尝试在 Haskell 中构建 FCA 类型的格型数据结构,我可以在其中检查两个实体是否有连接。实际上,我什至不确定晶格是正确的结构,因为它可能有点“太多”。
这是上下文。在 COBOL 程序分析器中,我有一个数据集名称、文件、记录和字段的本体。根据程序,一个数据集名称可以有多个文件名,一个文件可以有多个记录,一个记录可以有多个字段。我希望这种层次结构反映在 Haskell 数据结构中。但我也希望能够为 file1 和 file2 继承关系,以便我可以检查 file1 和 file2 是否属于相同的数据集名称。实际上,这种关系几乎可以是“==”的关系。但是,例如,它们可能只是在 dsn0 中有一个连接。
在这种情况下,我还有其他可以从格或 FCA 数据结构中受益的本体。例如,我有属于作业步骤的程序和属于作业的作业步骤。如果我能很容易地弄清楚两个程序是否属于同一个工作,那就太好了。在这里,它似乎也是一个“加入”运算符。获取某个实体的扩展名(代码)也会很有用。
我对 Haskell 还是有点陌生。我试图查看Lattice 库,但具体而言,我不确定从那里去哪里。知道如何开始吗?Haskell 中格子的一个小例子会很有帮助。非常感谢您的帮助(和耐心)。
更新:如评论中所述,Lattice 可能不是最好的形式。我意识到我可能只需要按照这些思路使用常规类类型的数据结构:
data DSN = DSN {
programFiles :: [ProgramFile]
name :: String
ddn :: DDN
}
data ProgramFile = ProgramFile {
records :: [Record]
name :: String
}
data Record = Record {
fields :: [Field]
name :: String
}
data Field = Field {
name :: String
order :: Int
}
我想我使用树/格/FCA 类型结构的最初意图是充分利用 Haskell 中的函子潜力,这应该会导致有趣的格操作,包括获得一个概念的所有扩展,检查两个概念是否属于相同的更高级别的概念,通过它们的 DSN 检查两个文件的相等性“==”,...
也许非二叉树结构会更好?在 Haskell 中很容易做到这一点吗?
解决方案
我建议创建一个抽象数据类型来表示一对多关系。它可能看起来像这样:
module OneToMany (OMRel, empty, insert, delete, source, targets) where
import Data.Map (Map)
import Data.Set (Set)
import qualified Data.Map.Strict as M
import qualified Data.Set as S
data OMRel a b = OMRel
{ oneToMany :: Map a (Set b)
, manyToOne :: Map b a
} deriving (Eq, Ord, Read, Show)
empty :: OMRel a b
empty = OMRel M.empty M.empty
insert :: (Ord a, Ord b) => a -> b -> OMRel a b -> OMRel a b
insert a b (OMRel otm mto) = OMRel
{ oneToMany = M.insertWith S.union a (S.singleton b) $
case M.lookup b mto of
Just oldA -> M.adjust (S.delete b) oldA otm
Nothing -> otm
, manyToOne = M.insert b a mto
}
delete :: (Ord a, Ord b) => a -> b -> OMRel a b -> OMRel a b
delete a b (OMRel otm mto) = OMRel (M.adjust (S.delete b) a otm) (M.delete b mto)
source :: Ord b => b -> OMRel a b -> Maybe a
source b = M.lookup b . manyToOne
targets :: Ord a => a -> OMRel a b -> Set b
targets a = M.findWithDefault S.empty a . oneToMany
(当然,您可以通过更高效的批量操作来充实 API,例如合并、批量插入、顺序组合等。但这是一种最小的构造/使用 API,可以让您到达您需要去的地方。)
然后你需要几个数据类型来表示你的各种本体条目:
newtype Dataset = Dataset { dataset :: String }
newtype Record = Record { record :: String }
newtype Field = Field { order :: Int }
从那里您可以使用具有类似类型的值OMRel Dataset FilePath
来表示数据集“包含”文件的事实。OMRel
对于查询包含相等性,您可以通过上面的 API一劳永逸地编写此代码:
sameSource :: (Eq a, Ord b) => OMRel a b -> b -> b -> Bool
sameSource rel b b' = source b rel == source b' rel
(如果两个缺失的目标应该被认为不相等,您可能需要一个额外的子句。)然后,例如,这可以专门用于
sameSource :: OMRel Dataset FilePath -> FilePath -> FilePath -> Bool
和朋友。
由于限制,您将无法创建Functor
(或Bifunctor
)实例。不过,我不清楚/是否对这个特定的数据结构有意义。例如,如果我们有关联and ,and ,那么应该关联or ?如果它们确实具有合理的解释并且有用,那么您可以采用 constrained-monads 方法,或者简单地提供一个从具有适当类型的模块命名的函数,但不使其成为实例方法。OMRel
Ord
fmap
bimap
x :: a <-> y :: b
x' :: a <-> y' :: b
f b = f b'
fmap f
f b
a
a'
bimap
OneToMany
推荐阅读
- c# - Tcp-Listener Doesnt Always Catch Connections
- python - Fast assignment to Cython memoryview
- git - Can I rollback "git checkout ."?
- sybase - How to use isql COLUMN Format option
- python - 如果存在基于另一个列值的行,Pandas 会删除一个列值
- matlab - unexpected behavior textscan matlab when skipping characters
- python-3.x - Gmail API How to retrieve body of an email
- c# - Web Api 如何处理这个查询字符串?
- python - 如何在熊猫数据框中找到标准匹配上方和下方的x行,然后将它们保存为新的df?
- arrays - scala中数组元素的组合