functional programming - Find Maximum from a Tree -


i trying find maximum number given tree:

(define-struct (some t)   ([value : t]))  (define-type (option t)   (u 'none (some t)))  (define-type bst (u 'e nd))  (define-struct nd   ([root : integer]    [lsub : bst]    [rsub : bst]))  (: maxi : bst integer -> integer) (define (maxi x acc)   (match x         ('e acc) ((nd ro ls rs)     (cond       ((> ro acc) (maxi ls ro))       (else        (maxi rs acc))))))

the above quote not work when enter following:

(maxi (nd 1 (nd 2 (nd 4 (nd 8 'e 'e) (nd 9 'e 'e)) (nd 5 'e 'e)) (nd 3 (nd 6 'e 'e) (nd 7 'e 'e))) 0)

can please help?

thank you!

so here test:

(maxi    (nd       1       (nd 2          (nd 4             (nd 8 'e 'e)             (nd 9 'e 'e))          (nd 5 'e 'e))       (nd 3          (nd 6 'e 'e)          (nd 7 'e 'e)))    0)

and here happens:

   acc  root   do?   ---------------------------------    0    1      go left acc = root    1    2      idem    2    4      idem    4    8      idem    8    e      return 8

if expect input trees satisfy binary search tree property, stating values on left subtree greater root , values of right subtree smaller or equal, test tree malformed bst, since 9 greater 4.

by way, if had bst, maximal value located?

if tree random tree, have compute maximum of both subtrees , root value before being able determine overall maximal value.

basically, want do:

(tree-max (nd root left right)) = (max root                                         (tree-max left)                                         (tree-max right))

if want recursively, encounter problem in base case because have provide maximal value empty leaf node: value pick make code incorrect tree contains values strictly below value. choose 0 , compute max of tree strictly negative numbers, 0 wrong answer because not appear in tree (what do?).

you can choose use accumulator instead of recursion, in case need 2 accumuators: maximum far , list of subtrees visit next. replace call stack heap-allocated stack.

i can't test following code, here possible implementation:

(define tree-max (tree greatest todo)   (match tree     ('e greatest (if (null? todo)                   greatest                  (tree-max (first rest)                             greatest                             (rest todo))     ((nd root left right) (tree-max left                                     (max greatest root)                                      (cons right todo))))

Comments

Post a Comment

Popular posts from this blog

sql server - Cannot query correctly (MSSQL - PHP - JSON) -

i have little problem on project. , turns out query result returns nothing when value of first name or last name has 'ñ' in it. here's code config.php: <?php ini_set('mssql.charset', 'utf-8'); header('content-type: text/html; charset=utf-8'); $servername = "192.168.1.21"; /* ip add of db server */ $connection = array("database" => "db", "uid" => "?", "pwd" => "***"); $conn = sqlsrv_connect($servername, $connection); if(!$conn){ echo "connection not established."; die(print_r(sqlsrv_errors(), true)); } ?> myquery: $idnumber = $_post["idnum"]; $response = array(); $query2 = "select clname, cfname, cmname, cqualifier student cidno = '$idnumber'"; try{ $stmt2 = sqlsrv_query($conn, $query2); } catch(pdoexeption $ex){ $response["success"] = 0; $response["message"] = "d...
Read more

php - trouble displaying mysqli database results in correct order -

i have table in database stores events , date expire. want display events on website display current events first expired events after? i have tried following sql $sql = "select noticeid, notice, noticedesc, noticeimg, noticedate, expirydate tbl_notices group noticeid ,expired order expirydate asc"; but returns expired results first due expirydate being ordered asc in query. my tbl_notice structure looks this noticeid => int(4) notice => varchar(100) noticedesc => text noticedate => timestamp noticeimg => varchar(40) expirydate => datetime expired => int(1) 0 current or 1 expired my php code is $sql = "select noticeid, notice, noticedesc, noticeimg, noticedate, expirydate tbl_notices group noticeid ,expired order expirydate asc"; $result = mysqli_query($conn,$sql); if ($result->num_rows > 0) { // output data of each row while($row = $result->fetch_assoc()) { ...
Read more

C++ Linked List -

i trying create linked list download txt file , use linked list handle file line line. when handling downloaded linked list operations performed on such text editor would. encountering problems however. seems "node(string value)" section of code has wrong though original node() declaration no arguments passes. unable figure out quite is. node.h class node { public: node(); node(string value); void setnext(node *nextnode); // allows user set "next" pointer of node points friend class linkedlist; private: string data; // data box node* next; // pointer box }; node.cpp # include <string> # include "node.h" using namespace std; node::node() { data = ""; next = null; } node::node(string value) { data = value; next = null; } void node::setnext(node *nextnode) // allows user set "next" pointer of node points { this->next = nextnode; } your #include <string> ...
Read more