Re: Dimension of sequences
CChris wrote:
>
> Igor Kachan wrote:
> >
> > Fernando Bauer wrote:
> > >
> > > Igor Kachan wrote:
> > > >
> > > > > 'non-rectangular sequence' (NRS) = all sequences that aren't RS.
> > > > > 'dimension of RS' = maximum depth of the sequence.
> > > > > 'dimension of NRS' = that is the question!
> > > >
> > > > Let's see the refman.doc file now.
> > > >
> > > > Robert Craig writes:
> > > >
> > > > "Sequences can be nested to any depth, i.e. you can have sequences
> > > > within
> > > > sequences within sequences and so on to any depth (until you run out
> > > > of
> > > > memory)."
> > > >
> > > > I see Rob cares just about *maximum* depth here, so his definition
> > > > of depht, documented in refman.doc, is strongly equivalent to your
> > > > definition of 'dimension of RS'.
> > > > Same thing, you just introduce some new term, synonym.
> > > >
> > > > No?
> > >
> > > Ok. We can use "depth" as synonym of "dimension" as you prefer. Then my
> > > question
> > > is:
> > > What is the depth of a NRS? How can I obtain it? For now, I only know the
> > > depth
> > > of a RS.
> >
> > Hello, Fernando!
> >
> > OK, let's use just that MaxDepth() function by Ricardo,
> > it seems to work properly not only on 'simple' sequences,
> > but on any ones, it is recursive, and gives us that
> > pure maximum maximorum depth of any sequence.
> >
> > See please:
> > }}}
<eucode>
> > global function MaxDepth(object o)
> > integer n, x
> > if atom(o) then
> > return 0
> > else
> > n = 0
> > for i = 1 to length(o) do
> > x = MaxDepth(o[i])
> > if x > n then
> > n = x
> > end if
> > end for
> > return n + 1
> > end if
> > end function -- it is function by Ricardo Forno, genfunc.e lib
> >
> > ? MaxDepth({{{{}}},{},{{},{{{{{{{{{{{{}}}}}}}}}}}}},{{{{{{{{}}}}}}}}})
> > ? MaxDepth({{{{1}}},{1},{{1},{{{{{{{{{{{{1}}}}}}}}}}}}},{{{{{{{{1}}}}}}}}})
> > </eucode>
{{{
> > The maximum depth is 14, all right.
> > Count please the '{' signs, opening the deepest sequence,
> > to be sure.
> > It seems to be a good parameter for description of a sequence.
> > Now a sequence has its own second dimension, and may be
> > considered as some 2-dimensional object, which can contain
> > description of any-dimentional real and unreal objects -
> > vectors, matrixes, tensors, lists, arrays, trees, books,
> > images ... etc, etc.
> > Sequence itself really has two own dimensions - length and depth,
> > I think now. So attempts to give it some *single* dimension
> > may be not very productive.
> >
> > > > Then, I do not think now that the 'rectangular' word is very
> > > > good for your purpose, maybe, 'regular', as some short
> > > > for 'regularly nested', is better.
> > > >
> > > Ok. But I think "rectangular" is sligthly more precise than "regular",
> > > since
> > > I could think that the following sequence is regular:
> > > repeat({1,{1,1}},n) where n is any integer number. And that sequence is
> > > NRS.
> > > Well, this is only a definition problem.
> >
> > Ricardo names these sequences as 'simple sequences'.
> >
> > > > > > So what? What will we do with all these new terms, with
> > > > > > all these new notions, with all these new concepts?
> > > > >
> > > > > First of all, they facilitate our communication, since we don't have
> > > > > to say
> > > > > that whole definition phrase.
> > > > > Second, the terms RS and NRS can represent types in Euphoria, like
> > > > > vector
> or</font></i>
> > > > > matrix, and so can be checked.
> > > > > Some algorithms can function with one and not with other type, etc..
> > > >
> > > > Ok, but for now I do not see some real place for the 'dimension' word
> > > > here. Length & Depth. These old good words are very clear in
> > > > the specific EU context.
> > >
> > > Ok. But the Depth concept is not so clear as it seems, since nobody
> > > defined
> > > what it is for NRS yet.
> >
> > OK, now we can calculate that Depth (good, let's name the maximum depth
> > as Depth) with Ricardo's function.
> >
> > Regards,
> > Igor Kachan
> > kinz at peterlink.ru
>
> Eu sequences model trees with atomic labels allowed, and mandatory, only on
> leaf nodes.
> For instance, {1,{2,3},4} is the same as
> root -> node1, node2, node3
> node1: 1
> node2 -> node4, node5
> node3: 4
> node4: 2
> node5: 3
>
> with hopefully obvious meaning of such a description of a tree.
>
> Now google for some litterature on trees. You'lll see that most specific form
> of trees define their own dimension, depth or height.
> Concepts that can be defined always include:
> * the depth of a tree, which is the height of its root;
OK, I like this theory very much as math at all, some good
thing to get crazy, if you do not have or do not like vodka, sorry. 
Why do they need these topsyturvy trees, Cris?
I can understand depth of a root and height of a tree,
but not on the contrary.
> * the depth of a node in a tree, which is its distance to the root (ie the
> number
> of edges to go from the node to the root);
> * the height of a node, which is the length of the longest path from the node
> to a leaf node in its subtree.
Same thing, very-very demonstrative concept.
> The length of a sequence is simply the number of children of the root. This
> has not much importance in tree theory, but is essential for _some_ sorts of
> them, namely strings of arbitrary things, among which trees. It has been
> chosen
> to build this special notion in the language, and to leave out the more
> general
> ones. Other trees will have their own notion of depth or somsuch, which
> depends
> on the speifics of the layout an uses of the given family of trees.
> So yes, sequences don't have a single dimension, although some sorts of
> sequences
> do have a more intinsic kind of dimension. Strings are an example, for which
> the length is the "natural" dimension.
OK, but depth of a string exists and is 1. So sequence seems to be
some 2-dimensional object anyway and always.
Regards,
Igor Kachan
kinz at peterlink.ru
|
Not Categorized, Please Help
|
|
