OpenEuphoria

Re: Homogeneous sequence

• Posted by Juergen Luethje <j.lue at gm??de> Aug 11, 2007
• 684 views

CChris wrote:

> Juergen Luethje wrote:
> 
> > Pete Lomax wrote:
> > 
> > > Juergen Luethje wrote:
> > > 
> > > > Hi all,
> > > > 
> > > > I want to have a user-defined type, that checks whether a variable is a
> > > > homogeneous sequence. With this, I mean a sequence which contains only
> > > > top-level elements of the same "structure".
> > > You realise this will fail if the table contains eg {name, salary} and the
> > > lengths
> > > of the names are not all the same?
> > > 
> > > There is a potentially exponential performance hit type-checking every
> > > element
> > > of a sequence like this. If length(table) is 1000 then a table[5]=x
> > > statement
> > > will rigorously type-check the other 999 elements.
> > > A possible solution is:
> > > 
> > > -- homogenous.e
> > > sequence the_table -- local, so no-one else can play with it
> > > 
> > > global type tableitem(sequence x)
> > >   if length(x)=2 and sequence(x[1]) and atom(x[2]) then
> > >      return 1
> > >   end if
> > >   return 0
> > > end type
> > > 
> > > global procedure replace(integer idx, tableitem x)
> > >   the_table[idx]=x
> > > end procedure
> > > 
> > > global funtion get_item(integer idx)
> > >   return the_table[idx]
> > > end function
> > > -- plus a host of similar functions to append, remove, insert etc 
> > > 
> > > In other words the_table is not itself type-checked, but all the
> > > operations
> > > allowed on it are. I accept that the above, while solving a particular
> > > performance
> > > problem, is rather cumbersome and does not easily scale well to handle
> > > multiple
> > > tables.
> > 
> > Thanks for the reply, Pete. I don't understand how it answers my
> > question, though. My origininal post probably was not very clear.
> > Here is the reason why I'm interested in all this:
> > 
> > A global library function shall operate on all elements of a list
> > which is passed to it as parameter. I'm not talking of tables, but the
> > list could contain _any_ type of elements, as long as all elements in
> > the list have the same "structure".
> > 
> > I want the function to do Euphoria sequence operations with all elements
> > of the list like this:
> > 
> > function foo (homogenous_sequence list)
> >    sequence z, list
> >    ...
> >    z = list[1]
> >    for i = 2 to length(list) do
> >       z += list[i]
> >    end for
> >    ...
> > end function
> > 
> > I want the elements of 'list' to be either all atoms or all sequences.
> > If all elements of 'list' are sequences, then their lengths must be the
> > same, ozherwise Eu sequence ops won't work. If the sequences contain
> > sub-sequences, their length must also be the same, I think.
> > 
> > So I'm looking for a good way to implement the user-defined type
> > 'homogenous_sequence', that checks whether either all elements of
> > 'list' are atoms, or all elements of 'list' are sequences with the
> > same lengths, and with the same order of atoms and sequences inside,
> > and all corresponding sub-sequences also must have the same lengths
> > and so on ...
> > 
> > Regards,
> >    Juergen
> 
> You are painfully aware that type checking has a O(N) complexity, where N is
> not the legth, but the number of all atoms in all your subsequences. Reguar
> type checking is probably very inefficient here.

O(N) complexity doesn't cause any pain for me.

> Where do you get the objects you are processing from? My first approach would
> be to have such objects come from "trusted" sources, where the creation
> process,
> being under your control, would guarantee the lengths being equal etc. faster
> than checking on an object as if you didn't know anything about it.
> If the objects come from data files you didn't control the creation, then...
> you have no choice indeed. Try to check each object once, so that you can
> considered
> ti as trusted later, avoiding any further check.

I want the user-defined type-checking for the parameter of a library
function, which is to be published. So it's not under my control in
which context people will use it, and from where they get their data.
That's actually the reason why I think it's a good idea to perform type-
checking on the parameter.
Also, we should be aware that in a library type-checking is only an
_offer_ to the user of the library. After debugging of the program,
type-checking should be turned off anyway.

Regards,
   Juergen