Nested lists [was Re: tree functions daily exercise: Table]

[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,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.