Counting/Getting "Level" of a hierarchical data

Question

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 ?

score 2 · Accepted Answer · answered Jun 28 '17 at 12:03

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.

I actually dont get any information if it should be breadth-first or another algorithm. The conditions are that some given testcases should work and that I am not allowed to use any other selfwriten functions.. your code looks good btw, I will look at it later when I'm home. Thank you for the answer — IPiiro, Jun 28 '17 at 12:28
Thats a point I assumed, that every element in the heap is unique. — typetetris, Jun 28 '17 at 12:33
Then I guess breath first is a reasonable solution. In its current form, the code still walks the whole tree for all branches without the element looked for. In a breadth-first scenario, it might be interesting to check all branches only to the current depth without any match - if you are looking for a challenge. I didn't have an immediate idea how to do this elegantly. — jan.vogt, Jun 28 '17 at 12:37

Counting/Getting "Level" of a hierarchical data

1 Answers1

Linked