Constraining lists, whose length is undetermined

[Torsten Anders]

Hi,

Thanks for the rapid answer! And sorry if my question was not stated clear 
enough. I try to do better. But this results in a somewhat lengthy mail, 
sorry.


I would like to do music composition / analysis with the means of Oz. A 
musical score may be represented by arbitrary nested records, as the example 
shows (seq and par represent containers, whose elements are sequential resp. 
parallel in time.):

seq(elements: [pause( duration: 2)
	        par(elements: [note(:pitch 48 duration: 2)
			    note(:pitch 55 duration: 2)])
	        par(elements: [note(:pitch 50 duration: 1)
			    note(:pitch 54 duration: 1)])])


I have an idea of how to search for a score, if only the element parameters 
(e.g. pitch and duration of notes) are looked for and the whole nested data 
structure (except those parameters) is already determined. 

But naturally you do not know the number of e.g. 'notes in a melody' before 
you wrote it. But you can restrict the number of notes in a melody by certain 
rules (e.g. the melody shall last 8 bars -- that way the number is dependend 
to the durations of all notes, which are restricted too somehow).


-----------------------------------------------------------------------------
|
|  following is a sketch of a program searching for the element
|  parameters in an otherwise determined score 
|  (This is not yet done in Oz, may therefor contain errors in 
|  reasoning. I just put it here to illustrate my quest):
|
|  define a score data structure (API)
|   * containers, elements and element parameters with bidirectional links
|   * various accessors incl. startTime, relations as successor (in a seq), 
|     simultaneous (in time)
| 
|  a constraint on a single score item can be expressed as a predicate 
|  (func of one arg, returns boolean) -- arbitrary relations between score
|  elements can be defined using accessors of the score API. 
|
|  these constraints will be "mapped" on score elements by special 
|  procedures (e.g. applying a constraint to all elements for the score 
|  or to all elements of a voice)
|
|  all element parameters are extracted (and possibly sorted) by a 
|  special procedure to be handed to the distribution procedure
|
|  special distribution techniques can be defined, accessing 
|  necessary information about the current score situation via the 
|  score accessors. E.g. a dynamic search order may distribute always
|  a parameters of a score element "leftmost in time": of the elements 
|  which have a determined start time (all elements in parallel, first 
|  element in sequence or elements which has a determined 
|  predecessor) find the elements with the least start time and 
|  distribute the domain of an undetermined parameter but first the 
|  duration)
|
-----------------------------------------------------------------------------


But as I said, usually the number of elements in a container shall be found 
during search as well. Therefore I asked: how may I constrain a list and its 
elements without knowing the list length before. I try to describe the 
question more formally.

A simplified example: 
I would like to do constrain a list and its elements. All elements of the 
list have a finite domain. The length of the list has a finite domain or/and 
is restricted by constraints to its elements. The domain of the list is the 
union of all possible element combinations (which is finite too).

A less simple example: 
I would like to use nested records to build up a tree (see example above). 
All leaves of the tree (element parameter) have a finite domain. The length 
of every list representing container elements has a finite domain or/and is 
restricted by constraints to its elements. The depth of nesting has a finite 
domain or/and is restricted by constraints to its content. The domain of a 
lists representing container elements is the union of all possible 
combinations of elements of that list. 

The full problem:
I would like to use nested records to build up a graph. Elements (e.g. notes) 
can be contained in multiple container hierarchies. Different container 
hierarchies represent different musical aspects (e.g. time position, harmonic 
analysis, grouping analysis etc.)


The score data structure is the same as in the sketch above. Also constraints 
are defined as sketched above: A constraint is a unary predicate on a score 
item, which will use the score API to express arbitrary relations between 
score items (e.g. that way a relation between neighboring notes in a voice 
may be defined [musicians call them voice leading rules]). These constraints 
will be somehow "mapped" on the score elements.

I do not know yet which distribution strategy will be appropriate.


Back to the simplified example (a list on unknown length):
My question is: what search mechanisms may I use in Oz to search a list 
whose length is undetermined (but restricted to a domain)? Are there perhaps 
predefined means to hand constraints to list elements? How may I distribute 
such a search space? 


Sorry for the length of the mail -- I hope I explained my question better ;-)

Thank you,
Torsten Anders


On Monday 28 January 2002 10:59, you wrote:
> Dear Torsten,
>
> what is it what you want to do. You want to compute with lists over
> which domain? What are the constraints over lists you are interested in?
> What are the kind of distribution strategies for lists you are
> interested in?
>
> Sorry, but I couldn't retrieve this information from your mail.
>
> Anyway, this has nothing to do with spaces (at least it appears to me).
>
>
> "Torsten Anders" <t.anders at nici.kun.nl> schrieb im Newsbeitrag
> news:<E16V8Hq-00061c-00.2002-01-28-09-41-15 at cmailENV3.svr.pol.co.uk>...
>
> > Hi,
> >
> > I am looking for a way to constraint a list (finally I am going to
>
> deal with
>
> > trees / graphs, but a list would be great as a first step). I do not
>
> know the
>
> > number of elements before, but the number shall be restricted by
>
> constraints.
>
> > To state a simple example: a variable is constrained to be a list of
>
> three
>
> > elements, every element is 1. The variable is not known to be a list
>
> before
>
> > search.
> >
> > I can not do this using FD constraints: you need to know the number of
> >
> > variables (and hand them to the distribution).
> >
> > Do I need to define an alternate search mechanism for this (using
>
> spaces)? Or
>
> > has anybody already worked on something related.
> >
> > Thank you
> > Torsten Anders
> > -
> > Please send submissions to users at mozart-oz.org
> > and administriva mail to users-request at mozart-oz.org.
> > The Mozart Oz web site is at http://www.mozart-oz.org/.
>
> -
> Please send submissions to users at mozart-oz.org
> and administriva mail to users-request at mozart-oz.org.
> The Mozart Oz web site is at http://www.mozart-oz.org/.
-
Please send submissions to users at mozart-oz.org
and administriva mail to users-request at mozart-oz.org.
The Mozart Oz web site is at http://www.mozart-oz.org/.