On 29.05.22 00:57, Waldek Hebisch wrote:
On Sat, May 28, 2022 at 11:45:26PM +0200, Ralf Hemmecke wrote:
Does anyone know why the original developers did not allow to copy a cyclic
list?
I guess, one could implement a copy that is again a cyclic list.
copy x ==
y := empty()
for k in 0.. while not empty? x repeat
k = cycleMax and cyclic? x => error "cyclic list"
y := concat(first x, y)
x := rest x
reverse! y
AFAICS there are pragmatic decisions based on execution time and
expected use cases. Years ago we had similar disscussion about
'length'.
OK, I guess, a suggestion to separate List intu a true finite list and a
PossiblyCyclicList is out of question? Is it?
I actually think that true lists are important enough to have a
true-list implementation that does not allow cycles.
Above one easily sees that in each iteration "copy" calls "cyclic?" and
cyclic? calls findCycle.
findCycle x ==
y := rest x
while not empty? y repeat
if eq?(x, y) then return x
x := rest x
y := rest y
if empty? y then return y
if eq?(x, y) then return y
y := rest y
y
That looks like copy(x) is O(n^2) where n=#x for ordinary lists.
The same would apply to "=" (in the generic implementation) if
there were no direct implementation
x = y ==
eq?(x, y) => true
while not empty? x and not empty? y repeat
Qfirst x ~=$S Qfirst y => return false
x := Qrest x
y := Qrest y
empty? x and empty? y
in List(S) itself (at the cost of running into an infinite loop for
cyclic lists).
Honestly, I am not happy about it, but being pragmatic could mean that
to fix the list(a..b by s) problem, it is enough to implement it
ignoring the possibility of cyclic structures.
Ralf
--
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 view this discussion on the web visit
https://groups.google.com/d/msgid/fricas-devel/1a3c5e5c-a8ac-683a-d1c6-2bb89adeecef%40hemmecke.org.
