haskell - Find the max value of node in a tree -

i have problem.

i have implement function maxt in haskell returns maximum value of node binary tree.

data tree = leaf | node (tree a) (tree a) 

this given. should next?

maxt :: (tree integer) -> integer maxt (leaf a) = maxt (node l r) = max (max (maxt l) (maxt r)) 

is right?

let's see how hard prove correct. why? because it's great way analyze programs errors. recursive ones. we'll technically use induction, isn't complex. key realize maxt t must largest value in tree t—this declaration, "maxt t must largest value in tree t" called invariant , we'll try prove it.

first, let's assume t leaf. in case, you've defined maxt (leaf a) = a , since there literally no other values in tree, a must largest. thus, maxt upholds our invariant when passed leaf. "base case".

---

now we'll consider happens when let t = node (leaf a) b (leaf c) integers a, b, , c. height-1 tree , forms might call "example case" induction. let's try out maxt , see if invariant holds.

maxt t  === maxt (node (leaf a) b (leaf c)) === max b (max (maxt (leaf a)) (maxt (leaf c))) 

at point we'll use our base-case step , since applications of maxt in expression on leafs each 1 must uphold our invariant. kind of dumb, that's because it's example case. we'll see more general pattern later.

for now, let's evaluate our maxt (leaf _) bits knowing result maximal value in each particular left- or right-subtree.

=== max b (max c) 

now, don't want dive definition of max, based on name i'm happy assume max b returns value maximal between a , b. pick our way through details here, it's clear max b (max c) has been given relevant information our node computing maximum of entire height-1 tree. i'd call successful proof maxt works both height-0 , height-1 trees (leafs , nodes containing leafs).

the next step generalize example case.

---

so let's apply same pattern generalizing on height of tree. we'll ask happens if fix number, n, , assume maxt t upholds our invariant t of height n or less. little bizarre—we have shown works n = 0 , n = 1. it'll clear why works little later.

so assumption us? well, let's take 2 trees of height n or less (call them l , r), integer x, , combine them form new tree t = node x l r. happens when maxt t?

maxt t === maxt (node x l r) === max x (max (maxt l) (maxt r)) 

and know, per our assumption, maxt l , maxt r uphold our invariant. chain of maxes continues uphold our invariant tree t that's height-(n+1). furthermore (and important) our process of assembling new trees general—we can make any height-(n+1) tree in method. means maxt works height-(n+1) tree.

---

induction time! know if pick n , believe (for reason) maxt works height-n tree, must work height-(n+1) tree. let's pick n = 0. know "base case" maxt works leafs, know maxt works height-1 trees. our "example case". now, given knowledge, can see maxt works height-2 trees. , height-3 trees. , height-4. , on , on , on.

this completes proof* maxt correct.

*i have leave few caveats. didn't fiddly details show max chains work out, though makes sense. didn't prove induction step works—what if there more ways make height-(n+1) tree using node on height-n or lesser trees? more powerful way "break apart" height-n tree, that's little harder see, think. finally, want think hard happens if send in maxt (leaf undefined) or other pathological values that. these arise in haskell because it's (turing-complete) computer language instead of pure math. honestly, these little bits don't change whole lot situation, though.