CODEWITHSUNDEEP
haskelltreepattern-matchingnodesprogramming-languages
user18674537
user18674537

Reputation:

Searching through a TrinaryTree in Haskell

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?

Upvotes: 1

Views: 156

Answers (1)

Chris
Chris

Reputation: 36536

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.

Upvotes: 2

Related Questions