www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - [Discussion] Endless lists

reply Sjoerd van Leent <svanleent wanadoo.nl> writes:
Hello all,

In some functional languages it is possible to have endless lists. Such 
lists are really with a length, but can be expanded when necessary.

This means that it is possible for example to define a function like:

int getCalculatedNumber(int index) {
	int[..] endless;
	if (endless[index] == 0) {
		endless[index] = index ^ 2;
	}
	return endless[index];
}

This is mainly handy for dynamic programming etc.

I don't mean to say that it needs to be a standard language feature 
(maybe it is better off as a library), I just want people to discuss the 
feature.

Regards,
Sjoerd van Leent
Nov 08 2004
next sibling parent reply Sean Kelly <sean f4.ca> writes:
In article <cmoi0d$r5i$1 digitaldaemon.com>, Sjoerd van Leent says...

In some functional languages it is possible to have endless lists. Such 
lists are really with a length, but can be expanded when necessary.

This means that it is possible for example to define a function like:

int getCalculatedNumber(int index) {
	int[..] endless;
	if (endless[index] == 0) {
		endless[index] = index ^ 2;
	}
	return endless[index];
}

This is mainly handy for dynamic programming etc.

I don't mean to say that it needs to be a standard language feature 
(maybe it is better off as a library), I just want people to discuss the 
feature.


So am I right in assuming that you mean an endless list would be declared as, in
this case:

int[..] endless;

where the '..' indicates that the list is endless.  And that any index operation
on such a list would succeed, perhaps by invisibly resizing the list?

Since D already supports resizable arrays, I don't see a huge advantage to
this--it would be easy enough to add some code to do this manually:

if( endless.length < index ) endless.length = index;

An alternative would be to use a dictionary as a sparse list:

int[int] endless;

This seems like it would make more sense as it eliminates the chance of a
OutOfMemoryError with code like this:

int x = getCalculatedNumber( 99999999999 );



Sean
Nov 08 2004
parent reply Sjoerd van Leent <svanleent wanadoo.nl> writes:
Sean Kelly wrote:

 In article <cmoi0d$r5i$1 digitaldaemon.com>, Sjoerd van Leent says...
 

In some functional languages it is possible to have endless lists. Such 
lists are really with a length, but can be expanded when necessary.

This means that it is possible for example to define a function like:

int getCalculatedNumber(int index) {
	int[..] endless;
	if (endless[index] == 0) {
		endless[index] = index ^ 2;
	}
	return endless[index];
}

This is mainly handy for dynamic programming etc.

I don't mean to say that it needs to be a standard language feature 
(maybe it is better off as a library), I just want people to discuss the 
feature.


 
 
 So am I right in assuming that you mean an endless list would be declared as,
in
 this case:
 
 int[..] endless;
 
 where the '..' indicates that the list is endless.  And that any index
operation
 on such a list would succeed, perhaps by invisibly resizing the list?
 
 Since D already supports resizable arrays, I don't see a huge advantage to
 this--it would be easy enough to add some code to do this manually:
 
 if( endless.length < index ) endless.length = index;


I think this would me the most usable manner to define an endless list. 
Wrapping it in a templated class would make it complete.


 
 An alternative would be to use a dictionary as a sparse list:
 
 int[int] endless;


Problem here is that the list does not actually resize. It only gets one 
new item each iteration an item is used which is inavailable. 
Nevertheless, it may be usable in some situations as well.


 
 This seems like it would make more sense as it eliminates the chance of a
 OutOfMemoryError with code like this:
 
 int x = getCalculatedNumber( 99999999999 );
 
 
 
 Sean


I am interested in this for creating a dynamic lookup table that 
enlarges itself when a new item needs to be added. I am looking for ways 
to perform a callback to a function that contains the logic to create 
the new item(s).

For example, if I would define a list that can have unlimited items, and 
a hit occurs which is at that moment out of bounds, the list would 
automatically call a delegated function that calculates the outcome that 
needs to be inserted in the location.

Regards,
Sjoerd
Nov 09 2004
parent Sean Kelly <sean f4.ca> writes:
Sjoerd van Leent wrote:

 
 I am interested in this for creating a dynamic lookup table that 
 enlarges itself when a new item needs to be added. I am looking for ways 
 to perform a callback to a function that contains the logic to create 
 the new item(s).
 
 For example, if I would define a list that can have unlimited items, and 
 a hit occurs which is at that moment out of bounds, the list would 
 automatically call a delegated function that calculates the outcome that 
 needs to be inserted in the location.


It's too bad D doesn't have reference types or you could do this:

alias int set( int[] a, int x ) {
     if( a.length < x ) a.resize( x + 1 );
     return a[x];
}

int[] endless;
endless.set( 9999 ) = 10;

I suppose you could use pointers, but that would make it less seamless.

Sean
Nov 09 2004
prev sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Sjoerd van Leent wrote:

 In some functional languages it is possible to have endless lists. Such
 lists are really with a length, but can be expanded when necessary.


As far as I know, endless lists in functional languages actually don't have
any length. Since (pure) functional languages don't know any assignment,
changing the lenght of a lists wouldn't be possible anyway.

Infinite lists as I remember them actually are what the name says: infinite
collections of values. Of course, these values cannot be stored but are
calculated on the fly.

Actually, in D, the equivalent to this would be a class overriding opIndex.
To the outside, it looks like a list, internally, it is calculated on the
fly.
Nov 08 2004
parent Sjoerd van Leent <svanleent wanadoo.nl> writes:
Norbert Nemec wrote:

 Sjoerd van Leent wrote:
 

In some functional languages it is possible to have endless lists. Such
lists are really with a length, but can be expanded when necessary.


 
 
 As far as I know, endless lists in functional languages actually don't have
 any length. Since (pure) functional languages don't know any assignment,
 changing the lenght of a lists wouldn't be possible anyway.
 
 Infinite lists as I remember them actually are what the name says: infinite
 collections of values. Of course, these values cannot be stored but are
 calculated on the fly.
 
 Actually, in D, the equivalent to this would be a class overriding opIndex.
 To the outside, it looks like a list, internally, it is calculated on the
 fly.
 


My definition of length of the lists here is meant to be physical. 
Hereby I mean that such lists are restrained by the physical limitations 
of a computer (memory bounds).

I was indeed having the idea to create a class that does this.

Regards,
Sjoerd
Nov 09 2004