tree functions daily exercise: Range

[Xah Lee]

Here's the belated Java solution.

import java.util.List;
import java.util.Array List;
import java.lang.Math;

class math {
public static List range(double n) {
return range(1,n,1);
}

public static List range(double n, double m) {
return range(n,m,1);
}

public static List range(double iMin, double iMax, double iStep) {
List ll = new ArrayList();
if (iMin <= iMax && iStep > 0) {
for (int i=0; i <= Math.floor((iMa x-iMin)/iStep); i++) {
ll.add(new Double(iMin+i*i Step));
}
return ll;
}
if (iMin >= iMax && iStep < 0) {
for (int i=0; i <= Math.floor((iMi n-iMax)/-iStep); i++) {
ll.add(new Double(iMin+i*i Step));
}
return ll;
}
// need to raise exception here
return ll;
}
}

class Range {
public static void main(String[] arg) {
System.out.prin tln(math.range( 5));
System.out.prin tln(math.range( 5,10));
System.out.prin tln(math.range( 5,7, 0.3));
System.out.prin tln(math.range( 5,-4, -2));
}
}

Perl & Python versions archived here:
http://xahlee.org/tree/tree.html

Xah
xa*@xahlee.org
∑ http://xahlee.org/
Dear functional programers,

i run services called a-python-a-day and a-java-a-day, where each day i

give a tip or snippet of code in these languages, also as a way for me

to learn these languages.

I've been running this perl-python a-day mailing list for several
months, and have accumulated a sizable tutorial here:
http://xahlee.org/perl-python/python.html

In the coming days, i'll be starting to translate a complete set of
tree processing functions. These functions, always takes a tree as
input (arbitrary nested list) and always returns a list of a definite
structure. Together, they form a particular functional programing
paradigm. See this page for the complete documentation as it exists
now:
http://xahlee.org/PerlMathemat ica_dir/Matica.html

As usuall, each day we will be spending about 20 minutes enjoying these

little exercises. If past experience is a good indication, then i
presume that in a month or two we will have built a complete set of
functions that manipulates tress, in languages Python and Java and
Perl. (the Perl set is already written)

I'm always interested in LISP and Haskell languages, but never
seriously learned them. I'm hoping that you functional programers in
these languages or learners, join me in these 15 minutes daily
exercises as a fun routine to learn languages or functional
programing.

I'm in particular very interested in the daily discussions of these
topics by functional programers, as well seeing such set of complete
code in scsh and Haskell. (Common Lisp or other functional languages
are always welcome of course)

Â* Xah
Â* [e-mail]
∑ http://xahlee.org/

[Xah Lee]

Here's the next tree functions exercise in Python, Perl, Java. Other
language solutions welcome.
http://xahlee.org/tree/tree.html
---------------------

Table('exprStri ng', [iMax]) generates a list of iMax copies of value
of
eval('exprStrin g'), and returns the refence to the list. i.e.
[eval('exprStrin g'),eval('exprS tring'),...]

Table('exprStri ng', ['i', iMax]) generates a list of the values by
evaluating 'exprString' when 'i' in the string runs from 1 to iMax.

Table('exprStri ng', ['i', iMin, iMax]) starts with 'i' = iMin.

Table('exprStri ng', ['i', iMin, iMax, iStep]) uses steps iStep. If
iStep
is negative, then the role of iMin and iMax are reversed. Inputs
such as
[1, -3 , 1] returns bad result.

Table('exprStri ng', ['i', iMin, iMax, iStep], ['j', jMin, jMax,
iStep],
... ) gives a array by iterating 'i', 'j' in 'exprString'. For
example,
Table('f(i,j)', ['i',1,3], ['j',5,6]) returns [[f(1, 5), f(1, 6)],
[f(2,
5), f(2, 6)], [f(3, 5), f(3, 6)]].

In general, Table has the form Table('expressi onString', iterator1,
iterator2, ...) where 'expressionStri ng' is a string that will be
evaluated by eval. iterator have one of the following forms [iMax],
['dummyVarString ',iMax], ['dummyVarString ',iMin, iMax], or
['dummyVarString ',iMin, iMax, iStep].

If Table fails, 0 is returned. Table can fail, for example, when
the
argument are not appropriate references or the iterator range is
bad
such as ['i',5,1].

Example:

Table('q(s)' ,[3]); # returns ['s','s','s']

Table( 'i**2' , ['i', 4]); # returns [1, 4, 9, 16]

Table('[i,j,k]',['i',2],['j',100,200,100],['k',5,6])
# returns [[[[1,100,5],[1,100,6]],[[1,200,5],[1,200,6]]],
# [[[2,100,5],[2,100,6]],[[2,200,5],[2,200,6]]]]
Wolfram Research's Table function documentation is at:
http://documents.wolfram.com/mathema...unctions/Table
(this post is not affliated with Wolfram Research Incorporated and has
not been approved by Wolfram Research Incorporated.)

The first argument of Table function in Mathematica (mma) is a
expression. Most other languages cannot have such symbolic expressions.
In Perl, a string is choosen instead as the experssion, and it is being
evalutade later as code. This may not be a practical choice but anyway
it's just a exercise. Each other language should choose appropriate
design for this emulation...

Perl, Python, Java solutions will be posted by me in the coming days.

Xah
xa*@xahlee.org
∑ http://xahlee.org/

[lqf]

thank

[Xah Lee]

The Perl version of the Tree function is posted. It's a bit long.
Please see the code here:
http://xahlee.org/tree/Table.html

the choice of having a string as the first argument to Table is a bit
awkward in Perl. Possibly i'll have to rewrite it so that the first
argument is a function instead, where in each iteration the the
variables are fed to the function. This necessarily breaks the
Mathematica's syntactical form of Table, and is slightly less flexible
in power, but is more natural and practical in non-symbolic languages
like Perl, Python, Java.

I think the goal of the whole tree functions project
http://xahlee.org/tree/tree.html
would make the code actually practically useful for processing trees in
each language, as opposed to sticking to uniformness of these functions
across languages.

later on, as we write more tree functions, the whole set will be very
useful in processing tree structures, such as XML and many other things
spurn from it today.

Disclaimer: this project is not affiliated with Wolfram Research Inc.

Xah
xa*@xahlee.org
∑ http://xahlee.org/

[Xah Lee]

here's the Python spec for the Table function:

'''Table(f,[iStart,iEnd,iSt ep]) returns a list of f applied to the
range range(iStart,iE nd,iStep).
Example: Table(f,[3,10,2]) returns [f(3),f(5),f(7), f(9)]
Table(f,[iStart,iEnd,iSt ep], [jStart,jEnd,jSt ep], ...) returns a nested
list of f(i,j,...) applied thru the iterators.
Example: Table(f,[1,3,1],[2,6,2]) returns [f(3),f(5),f(7), f(9)]'''

it is slightly shortcut from the full form in that it doesn't allow
short cut conveniences. For example, one should be able to write
Table(f,[i,4], [j,1,9,2])
for
Table(f,[i,1,4,1], [j,1,9,2])

anyhow, for simplicity, let's start with this simpler spec.

I started to code this problem but this is quite a large problem, so i
figured it'd be fruitful to discuss it as we go.

The first problem i noted is that in Python, one cannot assign elements
in arrays where it doesn't exist yet. i.e.
a[7]=2
is illegal. This is in contrast to Perl, where one can do:
$a[3][7][2]=4
and automatically have a 3-dimentional nested array, where other
members simply have undefined values.

(This behavior of Perl is convenient when needed, but i recall in 2001
i spend the whole half a day trying to debug a program and it turned
out is caused by this behavior.)

With perl, a solution is to have Table simply generate the following
text and eval it.
--------------
my ($i,$j,$k,);
my @resultArray;

foreach $i (0 .. scalar(@{$ref_r angeSequence->[0]}) -1 ) {
foreach $j (0 .. scalar(@{$ref_r angeSequence->[1]}) -1 ) {
foreach $k (0 .. scalar(@{$ref_r angeSequence->[2]}) -1 ) {
$resultArray[$i][$j][$k] = &{Function(\@pa rameterList,$ex prString)}
($ref_rangeSequ ence->[0]->[$i],$ref_rangeSequ ence->[1]->[$j],$ref_rangeSequ ence->[2]->[$k],);

};};};

return \@resultArray;
------------
(in the above code, note the line $resultArray[$i][$j][$k]=...)

Another issue noted is that the so-called “list comprehension†�
syntax construction in Python actually also contained a semantic
irregularity. That is to say, when the loops are nested inside a
list-comprehension, it still produced a flat list, instead of a nested
list.

This is quite a pain. I didn't realize this until i completed my code
and realized the result is a flat list. Here's the "wrong" code as a
result:

def Table2(fun, *itrs):
dim=len (itrs)
dummies = ['i'+repr(i) for i in Range(0,dim-1)]
ll = [ (dummies[i],itrs[i][0],itrs[i][1],itrs[i][2]) for i in
Range(0,dim-1)]
funString='f('
for i in dummies: funString += i + ','
funString = funString[0:len(funString )-1]
funString += ')'
loopStr= '[ ' + funString
for i in range(0,dim):
loopStr += ' for ' + dummies[i] + ' in Range(' +
repr(itrs[i][0])+','+repr(itrs[i][1])+','+repr(itrs[i][2]) + ') '
loopStr += ' ]'
print loopStr
return eval(loopStr)

I was happy thinking that i'm done until am really dismayed by a
realization of this semantic irregulary. Both syntax irregularity and
semantic irregularity are ubiquitous in imperative languages.

So, now i have two choices:

(1) add another code to make a structure out of a flat list.
e.g. turn [1,2,3,4,5,6] to [[[1,2]],[[3,4]],[[5,6]]]

(2) rewrite the Table function to not use list comprehension. Instead,
use for loops.

I started to do (1) by writing a separate Partition function... bun in
the process i think perhaps (2) is better...

----------------
References:

• for a context of this message, see: http://xahlee.org/tree/tree.htm

• for a exposition of syntax aspects of irregularity of Python's
“list-comprehension†�, see
http://xahlee.org/perl-python/list_comprehension.html

Xah
xa*@xahlee.org
∑ http://xahlee.org/

[Xah Lee]

the example in the spec of previous post is wrong. Here's corrected
version:

here's the Python spec for the Table function:

'''Table(f,[iStart,iEnd,iSt ep]) returns a list of f applied to the
range range(iStart,iE nd,iStep). Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7), f(9)] Table(f,[iStart,iEnd,iSt ep],
[jStart,jEnd,jSt ep], ...) returns a nested list of f(i,j,...) applied
thru the iterators. Example: Table(f,[1,3,1],[2,6,2]) returns
[[f(1,2),f(1,4),f (1,6)],[f(2,2),f(2,4),f (2,6)]]'''
it is slightly shortcut from the full form in that it doesn't allow
short cut conveniences. For example, one should be able to write
Table(f,[4], [1,9,2]) for Table(f,[1,4,1], [1,9,2])

Also, the first argument of expression has changed to a function
instead. Expression is much more convenient, but in languages that
isn't symbols oriented, a function is more appropriate.

anyhow, for simplicity, let's start with this simpler spec...

Xah
xa*@xahlee.org
∑ http://xahlee.org/

[Duncan Booth]

Xah Lee wrote:

'''Table(f,[iStart,iEnd,iSt ep]) returns a list of f applied to the
range range(iStart,iE nd,iStep). Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7), f(9)] Table(f,[iStart,iEnd,iSt ep],
[jStart,jEnd,jSt ep], ...) returns a nested list of f(i,j,...) applied
thru the iterators. Example: Table(f,[1,3,1],[2,6,2]) returns
[[f(1,2),f(1,4),f (1,6)],[f(2,2),f(2,4),f (2,6)]]'''

How does it know when to skip the end value (i.e. act as for the rest of
Python) and when to include it? Or did you mean:

Table(f,[1,3,1],[2,7,2]) returns
[[f(1,2),f(1,4),f (1,6)],[f(2,2),f(2,4),f (2,6)]]

Wouldn't it be more sensible just to take the iterators directly as
arguments, so for this example you would do:

Table(f, range(1,3), range(2,7,2))

That way you have more flexibility (e.g. to do out-of-order ranges such as
[1,3,2,0,4]), and the code for Table is much simpler since it just has to
manipulate the lists it was given.

[David Van Horn]

Xah Lee wrote:

here's the Python spec for the Table function: .... References:

• for a context of this message, see: http://xahlee.org/tree/tree.htm

Here is a Scheme implementation of Table. As noted on your web page and the
Mathematica documentation, the first argument of Table "evaluates in a
non-standard way". Thus we use Scheme macros to control the evaluation of
this expression. The first three clauses in this syntax definition take care
to fill in the default values for i, imin, and di when they are not provided.
The fourth clause iterates over one variable constructing a list. Notice
this is done tail-recursively. The last clause handles the multiple variable
case by rewriting the term into a simpler form.

(define-syntax table
(syntax-rules ()
((table exp (imax))
(table exp (i 1 imax 1)))

((table exp (i imax))
(table exp (i 1 imax 1)))

((table exp (i imin imax))
(table exp (i imin imax 1)))

((table exp (i imin imax di))
(let loop ((n imin) (accum '()))
(if (< imax n)
(reverse accum)
(loop (+ n di) (cons ((lambda (i) exp) n) accum)))))

((table exp i j ...)
(table (table exp j ...) i))))
;; Examples

(table #t (0)) ;; => '()
(table #t (5)) ;; => '(#t #t #t #t #t)
(table i (i 5)) ;; => '(1 2 3 4 5)
(table i (i 2 5)) ;; => '(2 3 4 5)
(table i (i 2 5 2)) ;; => '(2 4)
(table i (i 2 6 2)) ;; => '(2 4 6)
(table (add1 i) (i 2 6 2)) ;; => '(3 5 7)
(table (- i j) (i 2) (j 2)) ;; => '((0 -1) (1 0))

(table (list i j k) (i 2) (j 100 200 100) (k 5 6))
;; =>
'((((1 100 5) (1 100 6)) ((1 200 5) (1 200 6)))
(((2 100 5) (2 100 6)) ((2 200 5) (2 200 6))))

[Steven D'Aprano]

Removing cross-posts to java and scheme lists.

On Tue, 21 Jun 2005 01:54:40 -0700, Xah Lee wrote:

here's the Python spec for the Table function:

'''Table(f,[iStart,iEnd,iSt ep]) returns a list of f applied to the
range range(iStart,iE nd,iStep).
Example: Table(f,[3,10,2]) returns [f(3),f(5),f(7), f(9)]
Table(f,[iStart,iEnd,iSt ep], [jStart,jEnd,jSt ep], ...) returns a nested
list of f(i,j,...) applied thru the iterators.
Example: Table(f,[1,3,1],[2,6,2]) returns [f(3),f(5),f(7), f(9)]'''
Xah's specifications doesn't make sense.

He says that Table(f, ilist, jlist, ...) should return a nested list, but
then contradicts himself in the example, which is not a nested list. He
also doesn't explain what i and j are supposed to be. Since his specs make
no sense to me, I'll simply ignore them and use my own.

This demonstrates some interesting features of Python, in particular, the
way it can pack and unpack multiple arguments and how to produce nested
lists.
def table(f, start, end=None, step=1):
"""Returns a list of f applied to the range(start, end, step).

Like range(), table() accepts defaults for start and step
(zero and one respectively).
"""
if end is None:
# syntactic sugar allowing us to use a single
# argument for end
start, end = 0, start
return [f(x) for x in range(start, end, step)]

def table_nested(f, *args):
"""Returns a nested list of lists of f applied in turn to
each set of arguments.

Each argument is expected to be a list of no more than
three int arguments, suitable to use as arguments to range().

Example: table_nested(f, [0, 3, 1], [3, 10, 2]) returns
[[f(0), f(1), f(2)], [f(3), f(5), f(7), f(9)]]
"""
L = []
for arg in args:
L.append(table( f, *arg))
return L

py> nested_table(st r, [4], [3, 7], [3, 10, 2])
[['0', '1', '2', '3'], ['3', '4', '5', '6'], ['3', '5', '7', '9']]

<snip perl code>
Another issue noted is that the so-called "list comprehension"
syntax construction in Python actually also contained a semantic
irregularity. That is to say, when the loops are nested inside a
list-comprehension, it still produced a flat list, instead of a nested
list.
Wrong. Nesting list comprehensions two deep (list of lists) is simple.

py> [[x, x**2, 2**x] for x in range(4)]
[[0, 0, 1], [1, 1, 2], [2, 4, 4], [3, 9, 8]]

py> [range(n) for n in range(5)]
[[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]]

py> [range(n, n+4) for n in range(0, 16, 4)]
[[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15]]

Nesting three or more deep is harder, but not impossible.

def inner(n):
return [[x, x**2] for x in range(1, n+1)]
def outer(n):
return [[x, inner(x)] for x in range(1, n+1)]

py> outer(0)
[]
py> outer(1)
[[1, [[1, 1]]]]
py> outer(2)
[[1, [[1, 1]]], [2, [[1, 1], [2, 4]]]]

At the risk of making hard-to-maintain code, we can turn outer into a
single list comprehension:

def outer2(n):
return [[x, [[y, y**2 ] for y in range(1, x+1)]] for x in range(1, n+1)]
py> outer2(2)
[[1, [[1, 1]]], [2, [[1, 1], [2, 4]]]]
This is quite a pain. I didn't realize this until i completed my code
and realized the result is a flat list. Here's the "wrong" code as a
result:
Well, at least he realises that his code is wrong.
def Table2(fun, *itrs):
dim=len (itrs)
dummies = ['i'+repr(i) for i in Range(0,dim-1)]
ll = [ (dummies[i],itrs[i][0],itrs[i][1],itrs[i][2]) for i in
Range(0,dim-1)]
funString='f('
for i in dummies: funString += i + ','
funString = funString[0:len(funString )-1]
funString += ')'
loopStr= '[ ' + funString
for i in range(0,dim):
loopStr += ' for ' + dummies[i] + ' in Range(' +
repr(itrs[i][0])+','+repr(itrs[i][1])+','+repr(itrs[i][2]) + ') '
loopStr += ' ]'
print loopStr
return eval(loopStr)
What an awful mess.
I was happy thinking that i'm done until am really dismayed by a
realization of this semantic irregulary. Both syntax irregularity and
semantic irregularity are ubiquitous in imperative languages.

A poor craftsman blames his tools.
--
Steven.

[Xah Lee]

oops, another error. The example should be:

Table(f,[1,2,1],[2,6,2]) returns
[[f(1,2),f(1,4),f (1,6)],[f(2,2),f(2,4),f (2,6)]]

Wouldn't it be more sensible just to take the iterators directly as
arguments, so for this example you would do:

Table(f, range(1,3), range(2,7,2))
well yes... but this was emulation of Mathematica functions.
(Disclaimer: Mathematica is a trademark of Wolfram Research Inc, who is
not affliated with this project)

What you suggested is a function called Outer in Mathematica. The Table
function is in a sense multi-dimentional version of Range, so they
share syntax form.

Xah
xa*@xahlee.org
∑ http://xahlee.org/

Duncan Booth wrote: Xah Lee wrote:

'''Table(f,[iStart,iEnd,iSt ep]) returns a list of f applied to the
range range(iStart,iE nd,iStep). Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7), f(9)] Table(f,[iStart,iEnd,iSt ep],
[jStart,jEnd,jSt ep], ...) returns a nested list of f(i,j,...) applied
thru the iterators. Example: Table(f,[1,3,1],[2,6,2]) returns
[[f(1,2),f(1,4),f (1,6)],[f(2,2),f(2,4),f (2,6)]]'''

How does it know when to skip the end value (i.e. act as for the rest of
Python) and when to include it? Or did you mean:

Table(f,[1,3,1],[2,7,2]) returns
[[f(1,2),f(1,4),f (1,6)],[f(2,2),f(2,4),f (2,6)]]

Wouldn't it be more sensible just to take the iterators directly as
arguments, so for this example you would do:

Table(f, range(1,3), range(2,7,2))

That way you have more flexibility (e.g. to do out-of-order ranges such as
[1,3,2,0,4]), and the code for Table is much simpler since it just has to
manipulate the lists it was given.