如何定义安全约束玫瑰树
我试图定义一个具有以下特征的数据结构：
- 是一种玫瑰树
- ，树中的节点是变量排序的
- ，节点类型之间的唯一区别是对它们可以接受
- 的子节点数量的约束，完整的约束集是: None；OneOnly；TwoOnly；AtLeastOne；AtLeastTwo
- ，我希望相关约束是可校验的，并进行检查。(例如在构建或编辑树时，试图向IamJustOne :：OneOnly添加第二个子级是一个错误)
我很难开始定义这个结构(特别是3-5点)。
- 在web上有关于定义玫瑰树所需步骤的信息，
- 在Data.Tree.Rose中有足够的信息来创建具有可变节点的玫瑰树。(虽然我仍然不清楚Knuth树和Knuth forests.)
- There在该模块中的区别，但是Knuth forests.)
- There是关于异构容器的研究水平论文，远远超过了我的理解等级
。
我最初的方法是尝试将MyRose的子类型(不是工作代码)创建为：
data MyRose sub = MyRose {label :: String, subtype :: sub, children :: [MyRose sub]}
type AtLeastOne a = snoc a [a]
type AtLeastTwo a = snoc a ( snoc a [a] )
...
instance MyRose AtLeastOne where children = AtLeastOne MyRose -- instances to provide defaults
...
instance None STree where children = Nothing我尝试过各种使用数据、新类型、类、类型的方法，现在正在研究类型家族和数据家族。我的方法没有一种是有成效的。
您能给出定义此数据结构的指针吗？婴儿的第一步将是非常有用的--很难低估我在这个话题上的知识水平。
回答 2
Stack Overflow用户
发布于 2022-02-25 18:42:36
在你走疯狂的高级路线之前，我建议你确保简单的路线不够好。简单的路线如下：
data Tree = Node { label :: String, children :: Children }
data Children
= Zero
| One Tree
| Two Tree Tree
| Positive Tree [Tree]
| Many Tree Tree [Tree]这是你的标准：
constructor
- The
- 是一棵玫瑰树--嗯，我猜？？树中的
- 节点都是可变排序的--检查，五个
Children构造函数表示排序，而每个Children构造函数都可能对进行不同的选择，只有排序之间的不同是对它们可以接受的子级的限制-检查
- -完整的约束- check
- Relevant约束是类型可检查和检查-检查，例如，应用程序
One child1 child2不键入类型H 214G 215
Stack Overflow用户
发布于 2022-02-25 18:33:12
即使您可以定义它，这类树似乎也很难使用。树的类型必须反映它的整个结构，客户端必须在任何地方都携带该类型，因为树上的所有操作都需要知道这种类型才能做任何事情。他们不可能仅仅拥有一个Rose String之类的东西，他们需要知道确切的形状。
让我们想象一下你的目标已经成功了。然后，您可能有一些示例树t。
t :: OnlyTwo (AtLeastOne None)指示具有两个节点的顶层，每个节点至少有一个子节点，每个子节点都是空的。究竟insert t "hello"的类型应该是什么？deleteMin t的？如果删除单个节点，则无法真正知道树的哪些级别可能需要折叠；如果插入一个节点，则可能需要在何处增加一个级别。
也许您有这些问题的答案，以及一些模糊的用例，这是最好的解决方案。但是既然你要求婴儿的第一个解决方案:我想如果我是你，我会后退一步，问我为什么真的想要这个。您希望通过这个级别的类型细节实现什么？当客户端代码消耗或构建这样的树时，您希望它看起来像什么？这些问题的答案将使问题更加清楚。
https://stackoverflow.com/questions/71269318
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号