计数/获取“级别”的分层数据 [英] Counting/Getting "Level" of a hierarchical data
问题描述
我的问题是关于我的功课，我现在工作了几个小时。主题是功能数据结构，我有点卡住了，我不知道如何继续。
所以我需要用这个签名来写一个函数：
data Heap et = Heap {
包含:: e - > t e - >也许Int
}
为了说明这一点，我得到了一些像这样的变量：
x = 2
3 4
6 7 5
x =节点2（节点3（Node 6 Empty Empty）（Node 7 Empty Empty））（Node 4 Empty（Node 5 Empty Empty））
$ b $因为它是一些树数据。
包含堆2 x返回只是0
包含堆6 x返回只有2
包含堆42 x返回Nothing
所以如果整数在x的后面存在堆，contains将返回Just y，其中y是树的Level。在我的例子中：2级获得了0级，3级和4级是1级，依此类推。
这就是我的问题所在。我有一个函数可以说明整数是否在树中，但我不知道如何得到这个Level（我不知道怎么称呼它）。
我的函数如下所示：
contains = \et - >
（_，Empty）的情况（e，t） - > Nothing
（e，Node x t1 t2） - >
if e ==（head（heap2list heap（Node x t1 t2）））
then 0
else if（（包含堆e t1）==只是0）
那么只需0
else包含堆e t2
如果整数处于中，将返回只是0，否则没有。
顺便说一句，我不允许使用我自己编写的任何帮助函数。我允许使用的函数是：
empty :: te - 只返回一个空的堆
insert： ：e - > t e - > t e - 将元素插入堆
findMin :: t e - >也许e - 寻找一个堆中的最小值
deleteMin :: t e - >也许（t e） - 删除堆中的Min
merge :: t e - > t e - > t e - 合并2个堆
list2heap ::堆x t - > [x] - > t x - 将列表转换为堆
heap2list :: Heap x t - > t x - > [x] - 将堆转换为列表
给出这些函数。地图，foldl，foldr ...也是允许的。我试图保持这个问题的简短，所以如果缺乏任何信息，我已经准备好编辑它。
我会非常感谢任何帮助。请记住，这是一项家庭作业，我真的想自己做，并在这里问这个问题是我最后的选择。
工作代码：
contains = \et - >
（_，Empty）的情况（e，t） - > Nothing
（e，Node x t1 t2） - >
if e ==（head（heap2list heap（Node x t1 t2）））
then 0
else if（fmap（+1）（contains heap e t1））== Nothing
then（fmap（+1）（contains heap e t2））
else（fmap（+1）（contains heap e t1））
现在代码正在工作，所有的家庭作业条件都得到满足，但在我看来，它看起来像非常丑陋的代码。我可以以某种方式重新整理它吗？
问题是，规范目前不完整。解决方案应该是宽度优先还是左/右偏置深度优先算法？
仅使用Prelude功能的广度优先解决方案将是
- 示例数据结构
数据树e =节点e（树e）（树e）空
- 实际定义
包含e（节点c _ _）
| e == c = Just 0
包含
（Just a，Just b） - >的e（节点_l r）= fmap（+ 1）$ case（包含e l，包含e r）只需$ min a b
（Just a，_） - >只需
（_，b） - > b
包含_ Empty = Nothing
- 给定testdata：
x =节点2（节点3（节点6空的空））（节点7空的空）） （节点5空的空））
包含2 x - 只需0
包含6 x - 只需2
包含42 x - 无
- 未指定的例子：
- 1
- 1 1
- 1 2 1
- 2 1
- 2
x =节点1（节点1（节点1（节点2空空）空））（节点2空空））（节点1空（节点1空（节点1空（节点2空空）））
包含2 x - 只有2 =呼吸优先
包含2 x - 只有3 =左偏向深度优先
包含2 x - 刚刚4 =严重偏向深度优先
任何有偏向的深度优先都应该很容易得出。
Well I really don't know if this is the right title but I don't know how to call it else. My question is about my homework, I worked for a couple of hours now.The topic is "functional data structures" and I am kinda stuck at a point and I have no idea how to continue.
So I need to write a function with this signature:
data Heap e t = Heap {
contains :: e -> t e -> Maybe Int
}
To illustrate it, I got some variable like this:
x = 2
3 4
6 7 5
x = Node 2 (Node 3 (Node 6 Empty Empty) (Node 7 Empty Empty)) (Node 4 Empty (Node 5 Empty Empty))
So it is some "tree"-thing data.
contains heap 2 x returns Just 0
contains heap 6 x returns Just 2
contains heap 42 x returns Nothing
So if the integer behind "heap" exists in x, "contains" will return "Just y", where y is the "Level" of the tree. In my example: 2 got the Level 0, 3 and 4 are Level 1 and so on. And thats exactly where my problem is. I've got a function which can say if the integer is in the tree or not, but I have no idea how to get that "Level"(I don't know how to call it else).
My function looks like this:
contains = \e t -> case (e,t) of
(_,Empty) -> Nothing
(e , Node x t1 t2) ->
if e == (head (heap2list heap (Node x t1 t2)))
then Just 0
else if ((contains heap e t1) == Just 0)
then Just 0
else contains heap e t2
With that if the integer is in, it will return "Just 0" and else "Nothing". By the way, I am not allowed to use any "helper" functions written by myself. The function I am allowed to use are:
empty :: t e --Just returns an empty heap
insert :: e -> t e -> t e --insert an element into a heap
findMin :: t e -> Maybe e --find Min in a heap
deleteMin :: t e -> Maybe (t e) -- delete the Min in a heap
merge :: t e -> t e -> t e -- merges 2 heaps
list2heap :: Heap x t -> [x] -> t x -- converts a list into a heap
heap2list :: Heap x t -> t x -> [x] -- converts a heap into a list
these functions are given. map, foldl, foldr... are also allowed. I tried to keep the question short, so if any information lacking I'm ready to edit it.
I would be very thankful for any help. Please keep in my mind that this is a homework and I want really to do it on my own and asking this question here is my very last option.
Working Code:
contains = \e t -> case (e,t) of
(_,Empty) -> Nothing
(e , Node x t1 t2) ->
if e == (head (heap2list heap (Node x t1 t2)))
then Just 0
else if (fmap (+1) (contains heap e t1))== Nothing
then (fmap (+1) (contains heap e t2))
else (fmap (+1) (contains heap e t1))
Now the code is working and all the "homework-conditions" are fulfilled,but it looks like pretty ugly code in my opinion.. Can I refurbish it somehow ?
The problem is, that the specification is currently incomplete. Should the solution be a breadth-first or a left/right biased depth-first algorithm?
A breadth first solution using only Prelude functionality would be
-- Example data structure
data Tree e = Node e (Tree e) (Tree e) | Empty
-- Actual definition
contains e (Node c _ _)
| e == c = Just 0
contains e (Node _ l r) = fmap (+ 1) $ case (contains e l, contains e r) of
(Just a, Just b) -> Just $ min a b
(Just a, _) -> Just a
(_, b) -> b
contains _ Empty = Nothing
-- Given testdata:
x = Node 2 (Node 3 (Node 6 Empty Empty) (Node 7 Empty Empty)) (Node 4 Empty (Node 5 Empty Empty))
contains 2 x -- Just 0
contains 6 x -- Just 2
contains 42 x -- Nothing
-- unspecified example:
-- 1
-- 1 1
-- 1 2 1
-- 2 1
-- 2
x = Node 1 (Node 1 (Node 1 (Node 2 Empty Empty) Empty) (Node 2 Empty Empty)) (Node 1 Empty (Node 1 Empty (Node 1 Empty (Node 2 Empty Empty))))
contains 2 x -- Just 2 = breath-first
contains 2 x -- Just 3 = left biased depth-first
contains 2 x -- Just 4 = rigth biased depth-first
Any biased depth-first should be easily derived.
这篇关于计数/获取“级别”的分层数据的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
