Tree Functions: Table

Table

Here's the spec for Perl:

 Table('exprString', [iMax]) generates a list of iMax copies of value of
    eval('exprString'), and returns the reference 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]]]]

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 chosen instead as the expression, and it is being evaluate 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...

Solutions:

#! perl

# http://xahlee.org/tree/tree.html
# Xah Lee, 2005-05


#_____ Function _____ _____ _____ _____

=pod

B<Function>

Function(parameterList,'expressionString') returns a function. The
function takes parameters in parameterList and has body
expressionString. parameterList is a reference to a list of strings,
each represents a parameter name. For example: ['i','j']. The return
value of Function is a reference to a function.

Example:

&{Function(['i','j'],'i + j')}(3,4); # returns 7.

=cut

sub Function ($$) {
        my @parameterList = @{$_[0]};
        my $expression = $_[1];

        my $parameterDeclarationString = '(';

        foreach my $parameterString (@parameterList) {
        my $variable = '$' . $parameterString;
        $expression =~ s($parameterString)($variable)g;
        $parameterDeclarationString .= q($) . $parameterString . q(,);
        };

        chop($parameterDeclarationString);
        $parameterDeclarationString = q(my ) . $parameterDeclarationString . ')' . q(=  @_;);

        return eval("sub {$parameterDeclarationString; return ($expression);}");
};

#end Function

#_____ Range _____ _____ _____ _____

push (@EXPORT, q(Range));
push (@EXPORT_OK, q(Range));

# this version is written by tilt...@erols.com (Jay Tilton) ,Date: Sun, 15 May 2005 23:33:54 GM
sub Range {
    my( $a1, $b1, $dx ) =
        @_ == 1 ? (    1, $_[0], 1) :
        @_ == 2 ? ($_[0], $_[1], 1) :
        @_;
    if( $dx == 0 ) {
        warn "Range: increment cannot be zero.";
        return;
    }
    return [map $a1 + $dx * $_, 0..int( ($b1 - $a1) / $dx )];
};

#_____ UniqueString _____ _____ _____ _____

=pod

B<UniqueString>

UniqueString('aString', n) returns a reference to a list of n elements of strings, none of which are in the given string and no two are identical. Each string starts with 'unik' and followed by digits.

Example:

 UniqueString('Something about love...', 2);
 # returns ['unik23946', 'unik14135'].

=cut

# implementation note:
# Dependent functions: (none).

push (@EXPORT, q(UniqueString));
push (@EXPORT_OK, q(UniqueString));

sub UniqueString ($$) {
        my $input = $_[0];
        my $n = $_[1];

        my $str = 'unik' . int(rand()*10000*$n);
        my @result = ();
        for (my $i = 0; $i < $n; $i++) {
        while ($input =~ m($str)) {$str = 'unik' . int(rand()*10000*$n);}
        $input .= $str;
        push (@result, $str);
        };
        return \@result;
};

#end UniqueString


# _rangeSequence($ref_iteratorList) returns a sequence of ranges. For example, _rangeSequence([[-5,10,6],[3],[7,10]]) returns [[-5, 1, 7], [1, 2, 3], [7, 8, 9, 10]].
# Dependent functions: Range.
sub _rangeSequence ($) {
my $ref_iteratorList = $_[0];

my @result;
foreach my $ref_iterator (@$ref_iteratorList) {push(@result, Range(@$ref_iterator))};
return \@result;
};

#_____ Table _____ _____ _____ _____

# implementation note:
# gist: Generate a nested foreach loop, then evaluate this loop to get the result.

# First, get some basic info:

# @parameterList is of the form: ('i','j',...). If non exists, then a unique string is inserted. For example, if input is Table('expr',['i',4],[3]), then @parameterList is ('i','unik293');
# @iteratorList is of the form ([1,3],[2],[-2,7,3],...). It is the iterators without the dummy variable (if exists).
# $ref_rangeSequence is of the form [[1,...3],[1,...2],...]. It is the iterators expanded.

# Now, generate $stringToBeEvaluated. It has the following form (sample):

#foreach $h (0 .. scalar(@{$ref_rangeSequence->[0]}) -1 ) {
#foreach $unik5926 (0 .. scalar(@{$ref_rangeSequence->[1]}) -1 ) {
#foreach $gg (0 .. scalar(@{$ref_rangeSequence->[2]}) -1 ) {
#$resultArray[$h][$unik5926][$gg] = &{Function(\@parameterList,$exprString)} #($ref_rangeSequence->[0]->[$h],$ref_rangeSequence->[1]->[$unik5926],$ref_rangeSequence->[2]->[$gg],);
#};};};

# Dependent functions: UniqueString, _rangeSequence, Function.

sub Table ($;@) {
my $exprString = shift(@_);
my @iteratorList = @_;

my $depth = scalar(@iteratorList);
my @parameterList = ();

# set @parameterList and @iteratorList.
foreach my $ref_iterator (@iteratorList) {
if (scalar(@$ref_iterator) == 1) { push(@parameterList, ${UniqueString($exprString,1)}[0]);}
else { push(@parameterList, shift(@$ref_iterator));};
};

# Now, @parameterList is of the form ('i','j',...).
# Now, @iteratorList is of the form ([1,3],[2],[-2,7,3],...).

# $ref_rangeSequence is of the form [[1,...3],[1,...2],...].
my $ref_rangeSequence = _rangeSequence(\@iteratorList);

my $stringToBeEvaluated;
# generate a declaration of all the symbols. e.g. 'my ($i,$j,...); my @resultArray';
$stringToBeEvaluated .= 'my (';
foreach my $variable (@parameterList) {$stringToBeEvaluated .= '$' . $variable . ','};
$stringToBeEvaluated .= "); \n";
$stringToBeEvaluated .= 'my @resultArray;' . "\n\n";

#generate the beginning of for loops, $depth number of times. e.g. 'for $i (1..10) {'
        for my $i (0 .. $depth-1) {
        $stringToBeEvaluated .= 'foreach $' . $parameterList[$i] .
        ' (0 .. scalar(@{$ref_rangeSequence->[' . $i . ']}) -1 ) {' . qq(\n);
        };

#generate the heart of the loop. e.g. $array[$i][$j]... = f($i,$j,...);
        $stringToBeEvaluated .= '$resultArray';
        foreach my $variable (@parameterList) {$stringToBeEvaluated .= '[$' . $variable . ']';};
        $stringToBeEvaluated .= ' = &{Function(\@parameterList,$exprString)} (';
        for (my $i=0; $i<$depth; $i++) {$stringToBeEvaluated .=  '$ref_rangeSequence->[' . $i .
        ']->[$' . $parameterList[$i] . '],'
        };
        $stringToBeEvaluated .= "); \n";

#generate the ending of loops, $depth number of times. e.g. '};'
        $stringToBeEvaluated .= '};' x $depth . "\n\n";
        $stringToBeEvaluated .=  'return \@resultArray;';

#       debugging lines:
#       print qq(\$exprString is: $exprString\n);
#       print "\@parameterList is: @parameterList\n";
#       foreach my $ref_iterator (@iteratorList) {print "@\$ref_iterator is: @$ref_iterator\n"};
#       dumpValue($ref_rangeSequence);
        print "\n\n-----------------\n\n$stringToBeEvaluated------------\n";

#evaluate the stringToBeEvaluated to obtain the array. Return the result.
eval($stringToBeEvaluated);
};

#end Table


###########################################
# testing

use Data::Dumper;

print Dumper( Table('"f[i,j,k]"', ['i',3], ['j',3], ['k',3]) );

print 5;

Python

# -*- coding: utf-8 -*-
# Python

# http://xahlee.org/tree/tree.html
# Xah Lee, 2005-06

# Note the solution here is incomplete/incorrect.
# see http://xahlee.org/tree/Table_notes.html

import math;

def Range(iMin, iMax=None, iStep=None):
  if (iMax==None and iStep==None):
    return Range(1,iMin)
  if iStep==None:
    return Range(iMin,iMax,1)
  if iMin <= iMax and iStep > 0:
    if (isinstance(iStep,int) or isinstance(iStep,long)):
      return range( iMin, iMax+1, iStep)
    else:
      return [ iMin+i*iStep for i in range(int(math.floor((iMax-iMin)/iStep))+1) ]
  if iMin >= iMax and iStep < 0:
    if (isinstance(iStep,int) or isinstance(iStep,long)):
      return range( iMin, iMax-1, iStep)
    else:
      return [ iMin+i*iStep for i in range(int(math.floor((iMin-iMax)/-iStep))+1) ]
#  # raise error about bad argument
  return []

##############

def parti(l,j):
    '''parti(l,j) returns l partitioned with j elements per group. If j is not a factor of length of l, then the reminder elements are dropped.
    Example: parti([1,2,3,4,5,6],2) returns [[1,2],[3,4],[5,6]]
    Example: parti([1,2,3,4,5,6,7],3) returns [[1,2,3],[4,5,6]]'''
    n=len(l)/j
    r=[] # result list
    h=range(j) # temp holder for sublist
    for n1 in range(n):
        for j1 in range(j):
            h[j1]=l[n1*j+j1]
        r.append( h[:] )
    return r

# Terry Hancock hanc...@anansispaceworks.com, 2005-06
def parti2(L, j):
    return [L[k*j:(k+1)*j] for k in range(len(L)/j)]

##################

def Table(fun, *itrs):
    '''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,2,1],[2,6,2]) returns [[f(1,2),f(1,4),f(1,6)],[f(2,2),f(2,4),f(2,6)]]'''
    dim=len (itrs)
    dummies = ['i'+repr(i) for i in Range(0,dim-1)]
    i0=[0,1]
    i1=[2,3]
    i2=[4,'a']

    h0=[]
    for j0 in i0:
      h1=[]
      for j1 in i1:
        h2=[]
        for j2 in i2:
          h2.append(f(j0,j1,j2))
        h1.append( h2[:] )
      h0.append( h1[:] )
    return h0

def outer(fun, *lists):
    '''outer(f,list1, list2,...) is like Table(f,iterator1,iterator2,...)
except that in Table each iterator is generated by Range(), but in outer
the explicit list is given. For example, Table(f,[1,4,1],[2,6,2]) is
equivalent to outer(f,[1,2,3,4],[2,4,6])'''
    numLists=len (lists)
    dummies = ['j'+repr(i) for i in Range(0,numLists-1)]
    code=''
    print dummies
    obj=compile(code,'<string>','exec')
    result=0
    m='''
i0=[0,1]
i1=[2,3]
i2=[4,'a']

h0=[]
for j0 in i0:
  h1=[]
  for j1 in i1:
    h2=[]
    for j2 in i2:
      h2.append(f(j0,j1,j2))
    h1.append( h2[:] )
  h0.append( h1[:] )
return h0'''
    return result

def f(*a):
    return 'f'+repr(a)

print outer(f,[1,3,1],[1,3,1],[1,3,1])

# Table[f[i,j,k],{i,2},{j,3},{k,2}]
#{
#  {
#    {f[1,1,1],f[1,1,2]},
#    {f[1,2,1],f[1,2,2]},
#    {f[1,3,1],f[1,3,2]}
#  },
#  {
#    {f[2,1,1],f[2,1,2]},
#    {f[2,2,1],f[2,2,2]},
#    {f[2,3,1],f[2,3,2]}
#  }
#}

#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;

Some notes on writing this function in Python: Table_notes.html

Scheme version Table_scm.html