CODEWITHSUNDEEP
haskelltreedepth
Mert
Mert

Reputation: 55

Finding depth of tree haskell

I want to find the depth of an STree but in my code it won't count the first level.

data STree = SNode Label [STree] deriving (Eq,Show)

tdepth :: STree -> Label
tdepth (SNode _ [])= 0
tdepth (SNode l s) = 1 + naiveSumList([tdepth t | t <- s])

naiveSumList :: [Int] -> Label
naiveSumList (x:xs) = x + (naiveSumList xs)
naiveSumList [] = 0

tdepth SNode _ [] must give 1 but how can I count the levels? Here are the STrees I've been testing with:

s1 = SNode 1 []
s2 = SNode 1 [
        SNode 2 [],
        SNode 3 []
        ]
s3 = SNode 1 [
        SNode 2 [
            SNode 4 [],
            SNode 5 [],
            SNode 6 []
            ],
        SNode 3 []
        ]
s4 = SNode 1 [
        SNode 2 [
            SNode 4 [],
            SNode 5 [
                SNode 7 []
                ],
            SNode 6 []
            ],
        SNode 3 []
        ]

My results with code example:

tdepth s1  = 0
tdepth s2  = 1
tdepth s3  = 2
tdepth s4  = 3

And results should be:

 tdepth s1  = 1
 tdepth s2  = 2
 tdepth s3  = 3
 tdepth s4  = 4

Upvotes: 2

Views: 2241

Answers (1)

bheklilr
bheklilr

Reputation: 54058

Let's start with the base case. You want tdepth (SNode label []) to return 1, so let's write that case:

tdepth :: STree -> Int
tdepth (SNode _ []) = 1

Now we need to know how to compute the depth of a tree. The depth of a tree is the number of nodes on the longest branch, and your examples of what you expect out of your function are precisely what we're looking for. Since we're looking for the longest branch, we should be finding the maximum of the depth of each branch. Luckily, Prelude already has a maximum :: Ord a => [a] -> a function built in, so we can do

tdepth (SNode _ branches) = 1 + maximum [tdepth branch | branch <- branches]

Or equivalently (and the version I prefer)

tdepth (SNode _ branches) = 1 + maximum (map tdepth branches)

However, I don't like the parentheses around map tdepth branches, and since we're working with Int we can use the succ function that simply adds 1 to whatever Int is passed to it:

tdepth (SNode _ branches) = succ $ maximum $ map tdepth branches

But you can use whatever version you like, all three are pretty much equivalent.

All together we now have

tdepth :: STree -> Int
tdepth (SNode _ []) = 1
tdepth (SNode _ branches) = 1 + maximum (map tdepth branches)

I do have one more problem with this, we've repeated our logic for the depth of a single node, is there any way we can reduce this problem to where we Don't Repeat Ourselves? If instead of checking for the base case, we figure out a way to make maximum return 0 if branches == [], then our function wouldn't need two statements. Unfortunately, maximum currently errors if passed an empty list, but we can work around this pretty simply. All we have to do is ensure that the list passed to maximum always has at least one element in it:

tdepth :: STree -> Int
tdepth (SNode _ branches) = 1 + maximum (0 : map tdepth branches)
-- Or if you prefer
--                        = succ $ maximum $ 0 : map tdepth branches

We can safely prepend 0 onto our depths because we know our depth will always be greater than 0, so calling maximum on that list will return a valid result. Now we have a single expression that will calculate the depth of a tree accurately without having to handle any special cases.

Upvotes: 4

Related Questions