Re: Dimension of sequences
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
> > > > 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;
* 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.
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.
CChris
|
Not Categorized, Please Help
|
|
