Re: tree functions daily exercise: Table
Dear Dr Jon D Harrop, “List Comprehension” is a special concise syntax form that generates lists, as a way to save typing such as for loops. It is primarily a jargon bandied about by programers which have contributed huge misunderstandings and miscommunications. The extensiveness of this particular jargon's harm has also encroached into functional programing languages as to cause irregular syntax and less powerful semantics. The utility of “list comprehension” is just a (normal) function designed to generate list. References: • A exposition of list comprehension in Python. http://xahlee.org/perl-python/list_comprehension.html • Jargons of Info Tech Industry http://xahlee.org/UnixResource_dir/writ/jargons.html Xah [EMAIL PROTECTED] ∑ http://xahlee.org/ Jon Harrop wrote: David Hopwood wrote: That's consistent with the behaviour of list comprehensions in other languages -- including set/tuple formers in SETL http://www.cs.nyu.edu/~bacon/setl-doc.html, which I believe was the first language to support them. I don't know of any language where a list comprehension with multiple loops creates nested lists. I'm not entirely sure what a list comprehension is, but Mathematica might be an example of a language in which multiple loops create nested lists. -- Dr Jon D Harrop, Flying Frog Consultancy http://www.ffconsultancy.com -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
Dear Mr. Jones: Our team of 3,972 expert testers judged the output of your troll-spewing neural net virtually indistinguishable from the original. Given this, I am please to announce that our firm is willing to discuss arrangements for an exclusive license that you would likely find financially compelling. Please do not post the code on sourcefurge or whatever you call that open source thing until you speak with us. S. Ballmer -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
Xah Lee wrote: 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? -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
Duncan Booth wrote:
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):
Outer(f, range(1,3), range(2,7,2))
[[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()
--
--
http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
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([EMAIL PROTECTED],$exprString)}
($ref_rangeSequence-[0]-[$i],$ref_rangeSequence-[1]-[$j],$ref_rangeSequence-[2]-[$k],);
};};};
return [EMAIL PROTECTED];
(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
[EMAIL PROTECTED]
∑ http://xahlee.org/
--
http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
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 [EMAIL PROTECTED] ∑ http://xahlee.org/ -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
Xah Lee wrote: '''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. -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
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 -- http://mail.python.org/mailman/listinfo/python-list
Nested lists [was Re: tree functions daily exercise: Table]
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,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)]'''
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(str, [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.
--
http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
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 [EMAIL PROTECTED] ∑ http://xahlee.org/ David Van Horn wrote: 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
Xah Lee wrote: Very very nice! I don't know scheme well... but oh the macros, such a wonderful facility... Macros suck. They created by moron so-called computer scientists and IT puntits in order opress the programming masses. But I say we must bring freedom to all programmers. In order abolish this criminality against humanity and even programmers, I recommend creating a flurry of irrelevant messages cross-posting to noncommonalitous groups. If you need dictionary to find what that word means, you a moron! F*ck dictionaries! F*ck macros! F*ck ignoramous computer scientists! F*ck so-called netiquette! Power to programmers! Only when we have created sufficient confusion and frustration among all programming entities, then they will beg us to shut up. Only then they be willing remove macros from all languages if we willing shut up. Then we shut up and see macros removed. But only for a little while. Then we campaign to get floating point roman numerals implemented. Functional lang never let me down. Functional languages evil. Any language support functions come from ivory tower brain lacking idiots who think they know something. All other languages should take a lesson from Python which does not support functions. If Python supports functions, I have not read that informations. 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 [EMAIL PROTECTED] ∑ http://xahlee.org/ Power to programmers! JJ -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
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 [EMAIL PROTECTED] http://xahlee.org/ -- http://mail.python.org/mailman/listinfo/python-list
Re: tree functions daily exercise: Table
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
[EMAIL PROTECTED]
http://xahlee.org/
--
http://mail.python.org/mailman/listinfo/python-list
