Ralf Hemmecke wrote:
>
> On 07/04/2016 11:31 AM, oldk1331 wrote:
> >> With your suggestion of last: (SomeAggregate X, NNI) -> X, then
> >> with last([1,2,3,4,5,6],2) would I expect 5 or 4?
> >
> > We can define last(a,n) == first tail(a, n)
>
> I think it would make sense that "tail" and "last" and # and ... are
> only implemented if % has finiteAggregate.
>
> Oh, but wait. "tail" is not what one would think.
>
> tail : % -> %
> ++ tail(u) returns the last node of u.
> ++ Note: if u is \spad{shallowlyMutable},
> ++ \spad{setrest(tail(u), v) = concat(u, v)}.
>
> That looks like a technical definition meaning that (since internally
> even lists with a loop are stored with finitely many objects) one gets a
> link to the last object. However, if u is a structure of 2 elements that
> loop, i.e., the first element points to the second and the second back
> to the first, then the note is definitely wrong.
Both sides can not handle cyclic lists, so equality holds in
the sense that domains are equal and values on domain are equal.
>
> >> Ooops... I just looked into UnaryRecursiveAggregate. Such a structure
> >> can have loops. What would be the last element of a looped list that is
> >> [1,2,1,2,1,2,1,2,1,2,...].
> >
> > Currently # for a cyclic list will hang. Do you can that a problem?
>
> Since I didn't have need, I don't even know how to (officially) create a
> List that has a cycle. And if this is possible by the exported
> interface, then I don't understand what finiteAggregate
> (http://fricas.github.io/api/finiteAggregate) actually means.
> Is it meant to mean finite in the sense of finitely many stored objects
> or finite as a mathematical structure.
> A list that repeats 1,2,1,2,... is not finite for my taste even if it
> can be stored a list with one cycle, so it should not be a List(X).
For aggregates that are shallowlyMutable notion of finiteAggregate
is resonably clear: it is an aggregate that has finite number
of slots to store values. For recursive aggregates there are
some functions to navigate along aggregate ('rest' for lists,
'left' and 'right' for trees) and sequence of such functions
defines places. By modifying values stered in places you can
test if two places are the same or not. Aggregate is finite
if set of reachable places is finite (every path eventually
leads to alredy visited place). For immutable aggregates this
does not work, but FriCAS exposes 'eq?' which tests if to
places are the same or not. So you actually can algorithmically
check that aggregate is finite (of course, if aggregate is
infinite then attempted check will never finish).
Traditional data structures are acycylic and a lot of code
assumes acyclic structures without explicitely saying so
so I understand your doubts about cyclic lists. My view
is:
- cyclic lists have some uses
- it is very hard to staticaly avoid creating cyclic lists
and dynamic tests are expensive
- actual harm is quite low: most problems quickly show up
in testing and can be easily fixed
Given that I would say: list functions should support cyclic
lists when it is easy to do, but assume that lists are
acyclic otherwise. IMO attempts to bring more order here
have low payoff, we have bigger problem to handle.
--
Waldek Hebisch
--
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.
