[fricas-devel] [PATCH] Fix 'child?' and 'node?', use 'eq?' instead of '='

[oldk1331]

"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 <***@gmail.com>

+ * src/algebra/aggcat.spad, src/algebra/stream.spad:
+ src/algebra/tree.spad: Fix 'child?' and 'node?',
+ use 'eq?' instead of '='
+
[phone] Qian Yun <***@gmail.com>
+
* 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

[Waldek Hebisch]

Post by oldk1331
"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.

Well, this is controversial. Theoreticaly aggregate can be
represented in a compressed way and create nodes only on
demand, so that '=' is true, but not 'eq?'. More realistically
user my create a node which should be '=' to some node in
the aggregate and use say search to find position. With 'eq?'
such code would fail.

I am not sure if the two reasons above are important enough
to always use '='. But if we decide to use 'eq?' it would
need some big red scare in documentation. Also, bugs due to
using 'eq?' are likely to be hard to find. In the past
code used '=' and 'eq?' was limited to use as an optimization
(with appropriate care to avoid bugs).