Counting / getting "level" of hierarchical data
Well, I really don't know if this is the correct title, but I don't know what to call it. My question is about my homework, I have been working for several hours. The topic is "functional data structures" and I'm a little stuck at a certain point and I have no idea how to proceed.
So, I need to write a function with this signature:
data Heap e t = Heap {
contains :: e -> t e -> Maybe Int
}
To illustrate this, I got some variable:
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 this is some tree data.
contains heap 2 x returns Just 0
contains heap 6 x returns Just 2
contains heap 42 x returns Nothing
So, if an integer behind the heap exists in x, "contains" will return "Just y", where y is the "Level" of the tree. In my example: 2 got level 0, 3 and 4 got level 1, etc. And that's where my problem is. I have a function that can tell if an integer is in the tree or not, but I have no idea how to get this "level" (I don't know how to call it any other way).
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 this, if an integer is included, it will return "Just 0" and "Nothing". By the way, I am not allowed to use any of the "helper" functions I wrote. The function that I authorize to use:
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. card, crease, crease ... are also allowed. I tried to keep the question short, so if any information is not ready I am ready to edit it.
I would be very grateful for any help. Please remember that this is homework and I want to really do it myself and ask this question here, this is my 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" is done, but in my opinion it looks like pretty ugly code. Can I update it somehow?
source to share
The problem is that the specification is currently incomplete. Should the solution be a width at first or left / right offset depth algorithm?
The first solution using only the Prelude function 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 offset depth should be easily obtained.
source to share