tree functions daily exercise: Table

[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[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
 xah at xahlee.org
∑ http://xahlee.org/