"node?(u, v)" should return true only when they point to the same data structure, aka when they share part of data structure, so it should use 'eq?' instead of '='.
Because this is much more faster and fits well to functional programming style. Index: ChangeLog =================================================================== --- ChangeLog (revision 2519) +++ ChangeLog (working copy) @@ -1,5 +1,11 @@ 2018-11-20 Qian Yun <[email protected]> + * src/algebra/aggcat.spad, src/algebra/stream.spad: + src/algebra/tree.spad: Fix 'child?' and 'node?', + use 'eq?' instead of '=' + +2018-11-20 Qian Yun <[email protected]> + * src/algebra/aggcat.spad, src/algebra/tree.spad: Cleanup default implementation of 'leaves' and 'nodes' Index: src/algebra/aggcat.spad =================================================================== --- src/algebra/aggcat.spad (revision 2519) +++ src/algebra/aggcat.spad (working copy) @@ -1079,12 +1079,11 @@ ++ leaves(u) returns the list of leaves in aggregate \spad{u}. distance : (%, %) -> Integer ++ distance(u, v) returns the path length (an integer) from node u to v. - if S has BasicType then - child? : (%, %) -> Boolean - ++ child?(u, v) tests if node u is a child of node v. - node? : (%, %) -> Boolean - ++ node?(u, v) tests if node u is contained in node v - ++ (either as a child, a child of a child, etc.). + child? : (%, %) -> Boolean + ++ child?(u, v) tests if node u is a child of node v. + node? : (%, %) -> Boolean + ++ node?(u, v) tests if node u is the same as or contained in node v + ++ (either as a child, a child of a child, etc.). if % has shallowlyMutable then setchildren! : (%, List %) -> % ++ setchildren!(u, v) replaces the current children of node u @@ -1115,12 +1114,19 @@ if % has shallowlyMutable then setelt!(x, "value", y) == setvalue!(x,y) - if % has BasicType and S has BasicType then - child?(x, l) == member?(x, children(l)) if % has finiteAggregate then parts(x) == [value(i) for i in nodes(x)] + child?(u, v) == + empty? u or empty? v => false + any?(c +-> eq?(u, c), children v) + + node?(u, v) == + empty? u or empty? v => false + eq?(u, v) => true + any?(c +-> node?(u, c), children v) + )abbrev category BRAGG BinaryRecursiveAggregate ++ Author: Michael Monagan; revised by Manuel Bronstein and Richard Jenks ++ Date Created: August 87 through August 88 @@ -1192,13 +1198,16 @@ for y in children x repeat k := aggCount(y, k) k + child?(u, v) == + empty? u or empty? v => false + eq?(u, left v) or eq?(u, right v) + + node?(u, v) == + empty? u or empty? v => false + eq?(u, v) => true + node?(u, left v) or node?(u, right v) + if S has BasicType then - node?(u, v) == - empty? v => false - u = v => true - node?(u, left v) or node?(u, right v) => return true - false - x = y == empty?(x) => empty?(y) empty?(y) => false @@ -1522,6 +1531,18 @@ x := rest x copy x + child?(u, v) == + empty? u or empty? v => false + eq?(u, rest v) + + node?(u, v) == + empty? u or empty? v => false + for k in 0.. while not empty? v repeat + eq?(u, v) => return true + k = cycleMax and cyclic? v => error "cyclic list" + v := rest v + false + if % has finiteAggregate and S has BasicType then x = y == eq?(x, y) => true @@ -1532,14 +1553,6 @@ y := rest y empty? x and empty? y - node?(u, v) == - empty? v => false - for k in 0.. while not empty? v repeat - u = v => return true - k = cycleMax and cyclic? v => error "cyclic list" - v := rest v - u = v - if % has shallowlyMutable then setelt!(x, "first", a) == setfirst!(x, a) setelt!(x, "last", a) == setlast!(x, a) Index: src/algebra/stream.spad =================================================================== --- src/algebra/stream.spad (revision 2517) +++ src/algebra/stream.spad (working copy) @@ -319,10 +319,9 @@ cycleElt(x) case "failed" => false true - if S has SetCategory then - child?(x, y) == - empty? y => error "child: no children" - x = rst y + child?(x, y) == + empty? y or explicitlyEmpty? x => false + eq?(x, rst y) children x == empty? x => error "children: argument is empty" @@ -340,15 +339,15 @@ eq?(x, y) => error "distance: 2nd arg not a descendent of the 1st" - if S has SetCategory then - node?(z, x) == + node?(z, x) == -- error message only when x is a stream with lazy -- evaluation and 'y' is not a node of 'x' -- which has been computed when the function is called + explicitlyEmpty? z => return false y := x for i in 0.. repeat - z = y => return true explicitlyEmpty? y => return false + eq?(z, y) => return true lazy? y => error "node?: infinite stream" y := rst y if odd? i then x := rst x Index: src/algebra/tree.spad =================================================================== --- src/algebra/tree.spad (revision 2519) +++ src/algebra/tree.spad (working copy) @@ -76,9 +76,6 @@ value t == t case empty => error "cannot take the value of an empty tree" t.node.value - child?(t1, t2) == - empty? t2 => false - member?(t1, children t2) distance1(t1 : %, t2 : %) : Integer == t1 = t2 => 0 t2 case empty => -1 @@ -89,10 +86,6 @@ n := distance1(t1, t2) n >= 0 => n distance1(t2, t1) - node?(t1, t2) == - t1 = t2 => true - t2 case empty => false - any?((t : %) : Boolean +-> node?(t1, t), children t2) leaf? t == t case empty => false empty? children t -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/fricas-devel. For more options, visit https://groups.google.com/d/optout.
