tree functions daily exercise: Range

[Xah Lee]

Here's the belated Java solution.

import java.util.List;
import java.util.ArrayList;
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((iMax-iMin)/iStep); i++) {
ll.add(new Double(iMin+i*iStep));
}
return ll;
}
if (iMin >= iMax && iStep < 0) {
for (int i=0; i <= Math.floor((iMin-iMax)/-iStep); i++) {
ll.add(new Double(iMin+i*iStep));
}
return ll;
}
// need to raise exception here
return ll;
}
}

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

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

Xah
(e-mail address removed)
∑ 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 address removed)
∑ 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('exprString', [iMax]) generates a list of iMax copies of value
of
eval('exprString'), and returns the refence to the list. i.e.
[eval('exprString'),eval('exprString'),...]

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

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

Table('exprString', ['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('exprString', ['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('expressionString', iterator1,
iterator2, ...) where 'expressionString' 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/mathematica/functions/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
(e-mail address removed)
∑ 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
(e-mail address removed)
∑ http://xahlee.org/

 

[Xah Lee]

here's the Python spec for the Table function:

'''Table(f,[iStart,iEnd,iStep]) returns a list of f applied to the
range range(iStart,iEnd,iStep).
Example: Table(f,[3,10,2]) returns [f(3),f(5),f(7),f(9)]
Table(f,[iStart,iEnd,iStep], [jStart,jEnd,jStep], ...) 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_rangeSequence->[0]}) -1 ) {
foreach $j (0 .. scalar(@{$ref_rangeSequence->[1]}) -1 ) {
foreach $k (0 .. scalar(@{$ref_rangeSequence->[2]}) -1 ) {
$resultArray[$i][$j][$k] = &{Function(\@parameterList,$exprString)}
($ref_rangeSequence->[0]->[$i],$ref_rangeSequence->[1]->[$j],$ref_rangeSequence->[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,itrs[0],itrs[1],itrs[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 + ' in Range(' +
repr(itrs[0])+','+repr(itrs[1])+','+repr(itrs[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
(e-mail address removed)
∑ 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,iStep]) returns a list of f applied to the
range range(iStart,iEnd,iStep). Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7),f(9)] Table(f,[iStart,iEnd,iStep],
[jStart,jEnd,jStep], ...) 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
(e-mail address removed)
∑ http://xahlee.org/

 

[Duncan Booth]

'''Table(f,[iStart,iEnd,iStep]) returns a list of f applied to the
range range(iStart,iEnd,iStep). Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7),f(9)] Table(f,[iStart,iEnd,iStep],
[jStart,jEnd,jStep], ...) 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]

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))))

 

[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
(e-mail address removed)
∑ http://xahlee.org/

'''Table(f,[iStart,iEnd,iStep]) returns a list of f applied to the
range range(iStart,iEnd,iStep). Example: Table(f,[3,10,2]) returns
[f(3),f(5),f(7),f(9)] Table(f,[iStart,iEnd,iStep],
[jStart,jEnd,jStep], ...) 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.

 

[alex goldman]

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)

You could have fooled me.

 

[Xah Lee]

Very very nice! I don't know scheme well... but oh the macros, such a
wonderful facility...

Functional lang never let me down.

I haven't worked on a Java version yet... but i wonder what pain i'll
have to endure for a lang that lacks eval. Since i'm not Java expert...
i wonder if i can even do it in a few days.

Xah
(e-mail address removed)
∑ http://xahlee.org/

 

[Duncan Booth]

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.

Ok, so, if I understand you, the definition of Table is just:

def Table(f, *lists):
return Outer(f,
*[range(start,end+1,step) for (start,end,step) in lists])

Is that about right?

 

[Duncan Booth]

Ok, so, if I understand you, the definition of Table is just:

def Table(f, *lists):
return Outer(f,
*[range(start,end+1,step) for (start,end,step) in lists])

Is that about right?

And lest you think I left a bit too much as an "exercise for the
reader":

-------------- xah.py --------------------
def Table(f, *lists):
"""Xah Lee's Table function

Table(f,[3,10,2]) [f(3), f(5), f(7), f(9)]
Table(f,[1,2,1],[2,6,2])

[[f(1, 2), f(1, 4), f(1, 6)], [f(2, 2), f(2, 4), f(2, 6)]]
"""
return Outer(f, *[range(start,end+1,step) for (start,end,step) in lists])

def explode(lists):
"""Form all combinations of 1 element from each list.

explode([[1,2], [3]]) [(1, 3), (2, 3)]
explode([[1,2], [3,4]]) [(1, 3), (1, 4), (2, 3), (2, 4)]
explode([[1,2], [3,4], [5]])

[(1, 3, 5), (1, 4, 5), (2, 3, 5), (2, 4, 5)]
"""
result = [()]
for l in lists[::-1]:
result = [ (val,) + tail for val in l for tail in result ]

return result

def groupsOfN(it, n):
"""Returns tuples of length n taken from it.

groupsOfN(range(12), 3) [(0, 1, 2), (3, 4, 5), (6, 7, 8), (9, 10, 11)]
groupsOfN(range(12), 1)

[(0,), (1,), (2,), (3,), (4,), (5,), (6,), (7,), (8,), (9,), (10,), (11,)]
"""
it = iter(it)
return zip(*([it]*n))

def Outer(f, *lists):
"""[[f(1, 2), f(1, 4), f(1, 6)], [f(2, 2), f(2, 4), f(2, 6)]]
"""
result = [f(*args) for args in explode(lists)]
for l in lists[:0:-1]:
result = [list(v) for v in groupsOfN(result, len(l))]
return result

def _test():
global f
class f:
def __init__(self, *args):
self.args = args
def __repr__(self):
if len(self.args) == 1:
return "%s(%r)" % (self.__class__.__name__.split('.')[-1], self.args[0])
else:
return "%s%r" % (self.__class__.__name__.split('.')[-1], self.args)

import doctest
doctest.testmod()

if __name__ == "__main__":
_test()
------------------------------------------