CODEWITHSUNDEEP
haskellbinary-search-tree
Wornz94
Wornz94

Reputation: 31

delete empty nodes from tree

I want to implement a function which deletes any empty children in a tree:

makeUnhollow (Node 5 Empty Empty) => Leaf 5
makeUnhollow (Leaf 5) => Leaf 5
makeUnhollow (Node 5 (Leaf 4) Empty) => (Node 5 (Leaf 4) Empty)

This is my current code:

makeUnhollow :: Tree a -> Tree a
makeUnhollow  (Node a Empty Empty)= Leaf a
makeUnhollow (Leaf a) = Leaf a
makeUnhollow a = a

But somehow I'm getting failures for this code:

Tests.hs:130:
wrong result
expected: Node 6 (Leaf 5) (Leaf 7)
but got: Node 6 (Node 5 Empty Empty) (Node 7 Empty Empty)

Upvotes: 2

Views: 280

Answers (1)

sshine
sshine

Reputation: 16105

Deleting all Empty children in a tree seems a little difficult:

  • Node a Empty Empty can become Leaf a
  • What if your root node is Empty?
  • What will Node a Empty (Leaf b) be?

I understand from your test that your goal is just to turn Node a Empty Empty into Leaf a, and not care when only one child is Empty. Mark Seemann's suggestion to turn makeUnhollow into a recursive function means you have to make it call itself in the last case of:

makeUnhollow :: Tree a -> Tree a
makeUnhollow (Node a Empty Empty) = Leaf a
makeUnhollow (Leaf a) = Leaf a
makeUnhollow Empty = ?                --  don't forget to match Empty
makeUnhollow (Node a left right) = ?  --  recurse on left, right :: Tree a

I might just call the function unhollow since that's an imperative verb, too.

Upvotes: 3

Related Questions