Searching through a TrinaryTree in Haskell

Admin 1
Viewed 143

I am trying to search through a TriTree.

I have this type for my Tree and here's my search function for NodeTwo:

data TriTree a
  = Empty
  | NodeOne a (TriTree a) (TriTree a) (TriTree a)
  | NodeTwo a a (TriTree a) (TriTree a) (TriTree a)
  deriving (Show)

search :: Ord a => a -> TriTree a -> Bool
search _ Empty = False
search x (NodeOne v a b c) = x == v || x `search` a || x `search` b || x `search` c
search x (NodeTwo u v a b c) = x == u || x == v || x `search` a || x `search` b || x `search` c
search x _ = undefined

Someone else had the same question; we're given the type but need to implement search. Is the search function I implemented for NodeTwo is valid? Is it even pattern matching if this doesn't handle both NodeOne and Node two within one call?

tree nodes pattern-matching programming-languages haskell
1 Answers

By the time you write search x _ = undefined you have matched all possible cases already, so this is unnecessary. Your compiler should warn you that the pattern is redundant.

Otherwise this appears to work quite well. To my eye you've done this the right way using pattern-matching to handle TriTree values constructed using Empty, NodeOne, or NodeTwo.

These three clauses do belong to one and the same function definition, so they do handle all three possible cases "within one call". This can be seen clearer when re-written as the equivalent one case ... of ... expression.

user_152613150
Related