map/filter/reduce/lambda opinions and background unscientificmini-survey

[Christopher Subich]

concept quickly familiar. But "lambda" has a very clear meaning... it's
a letter of the greek alphabet. The connection between that letter and
anonymous functions is tenuous at best, and fails the test of making
Python read like "executable pseudocode".

But 'lambda' does have a very clear meaning in the realm of functional
programming, and it means precisely (mostly) what it means in Python: an
anonymous function.

It might not be the -best- possible name, but anyone who's had a
computer science education should have had a class that introduced basic
functional programming topics (even if only for academic interest), and
so they should be familiar with the keyword name.

If not, then it's just a magic word. Kind of like 'def'.

 

[mcherm]

Up until a few years ago, I ran the computer science department at a
high-school. I provided support for the English teachers who taught
*all* students -- but they taught things like the use of a word
processor or the internet, and never covered the meaning of "lambda". I
taught a computer applications course which was taken by only small
fraction of the students (<10%) but there I taught things like the use
of photo-editing software, creating web sites, and the use of simple
databases; I never covered the meaning of "lambda". I also taught the
programming class (taken by only a dozen or so students per graduating
class) -- students learned basic concepts like variables, looping, up
through fancier bits like a couple different sorting algorithms. But I
didn't cover the meaning of "lambda". And I also taught the "AP"
computer course (taken by an average of just 4 students per year!), in
which I explained things like object oriented programming and recursion
and managed to get the students to the level where they could work
together as a group to write a moderately complex program, like a
simple video game. And I didn't teach the meaning of "lambda", nor was
it covered by the "AP" exam, which is supposed to be equivalent to a
single college-level course in computer programming.

So I'd say that it's a pretty obscure name that most people wouldn't
know.

And besides, "def" isn't a "magic" word... it's an abreviation for
"define"... I hope that any student who didn't understand a word as
common as "define" wouldn't have graduated from our school.

-- Michael Chermside

 

[Peter Hansen]

So I'd say that it's a pretty obscure name that most people wouldn't
know.

It would be hard to argue against that statement; certainly "lambda" in
this context (or probably any) is not a word "most people" would know.

On the other hand, the name itself is probably not very important. I
still remember my first encounter with "lambda" in Python very clearly.

I saw the word, thought "huh? what the heck is that?", then read a
sentence about it that included some comment about its background in
other fields.

"Oh," I said, "pre-existing usage. Whatever." I proceeded to read
about what it did and how to use it.

The name was irrelevant. If the text had said "anonymous functions are
created using the keyword 'tribble' (named for a similar feature in a
fictional Klingon programming language)", I wouldn't have felt any
differently about it. So it makes some sense to a few trekkers... big
furry deal.

What bothered me was the syntax. Arguments without parentheses? What
possessed anyone to put something so inconsistent in the language? No
statements? Dang, that will limit my interest in using them. Oh well,
what's page four of the tutorial got for me next? It shouldn't take
anyone more than ten seconds to integrate "lambda" into their brain and
carry on with useful work.

Really, the name is such a trivial, unimportant part of this whole thing
that it's hardly worth discussing. The syntax is more important, and
the limitations are of definite interest. Not the name.

-Peter

 

[Grant Edwards]

Up until a few years ago, I ran the computer science department at a
high-school. I provided support for the English teachers who taught
*all* students -- but they taught things like the use of a word
processor or the internet,

That's not computer science.

and never covered the meaning of "lambda". I taught a computer
applications course which was taken by only small fraction of
the students (<10%) but there I taught things like the use of
photo-editing software, creating web sites, and the use of
simple databases;

That's not computer science.

I never covered the meaning of "lambda". I also taught the
programming class (taken by only a dozen or so students per
graduating class) -- students learned basic concepts like
variables, looping, up through fancier bits like a couple
different sorting algorithms.

Now you're getting a little closer to computer science.

It sounds like you ran a computer user training department. I
don't think it could be called computer science.

But I didn't cover the meaning of "lambda". And I also taught
the "AP" computer course (taken by an average of just 4
students per year!), in which I explained things like object
oriented programming and recursion and managed to get the
students to the level where they could work together as a
group to write a moderately complex program, like a simple
video game. And I didn't teach the meaning of "lambda", nor
was it covered by the "AP" exam, which is supposed to be
equivalent to a single college-level course in computer
programming.

Computer programming isn't the same thing as computer science.
It's just one of the tools used to do computer science.

So I'd say that it's a pretty obscure name that most people
wouldn't know.

I can't believe that anybody with any computer science
background doesn't know it.

And besides, "def" isn't a "magic" word... it's an abreviation
for "define"... I hope that any student who didn't understand
a word as common as "define" wouldn't have graduated from our
school.

Lamda isn't a magic word either. It comes from lambda
calculus.

 

[Sybren Stuvel]

Grant Edwards enlightened us with:

It sounds like you ran a computer user training department. I don't
think it could be called computer science.

Being a computer science student at the University of Amsterdam, I can
tell you that it definitely should not be called "computer science".

I can't believe that anybody with any computer science background
doesn't know it.

I agree.

Sybren

 

[Devan L]

def flatten(iterable):
if not hasattr(iterable, '__iter__'):
return [iterable]
return sum([flatten(element) for element in iterable],[])
Recursion makes things so much shorter.

 

[George Sakkis]

def flatten(iterable):
if not hasattr(iterable, '__iter__'):
return [iterable]
return sum([flatten(element) for element in iterable],[])
Recursion makes things so much shorter.

The last line can faster and more compact by:

from itertools import imap

def flatten(iterable):
if not hasattr(iterable, '__iter__'):
return [iterable]
return sum(imap(flatten,iterable),[])

George

 

[Tom Anderson]

Having said that, I too will miss the *concept* of an anonymous
function, although I wouldn't mind at all if its name changed, or if it
were somehow integrated into the "def" keyword's usage. Using backticks
or some other syntax delimiter also sounds promising, although we're
sort of running out of them. ;-)

I understand that the backslash is popular in some ivory-tower functional
languages. Currently, a backslash can be used for explicit line joining,
and is illegal elsewhere on a line outside a string literal, so i think
it's available for this. It would be utterly unpythonic to use puntuation
instead of a keyword, and it would make no sense to novices, but it would
scare the crap out of C programmers, which has to be worth something.

tom

 

[Ivan Van Laningham]

Hi All--

I understand that the backslash is popular in some ivory-tower functional
languages. Currently, a backslash can be used for explicit line joining,
and is illegal elsewhere on a line outside a string literal, so i think
it's available for this. It would be utterly unpythonic to use puntuation
instead of a keyword, and it would make no sense to novices, but it would
scare the crap out of C programmers, which has to be worth something.

Oh, I don't think so. Don't forget that Perl was written by impatient C
programmers. I think scaring C programmers, like giving engineers too
much information, is really hard to do. Live by the sword, die by the
sword.

Metta,
<int *(*(*foo)())()>-ly y'rs,
Ivan
----------------------------------------------
Ivan Van Laningham
God N Locomotive Works
http://www.andi-holmes.com/
http://www.foretec.com/python/workshops/1998-11/proceedings.html
Army Signal Corps: Cu Chi, Class of '70
Author: Teach Yourself Python in 24 Hours

 

[Ron Adam]

The trouble with these is that they make a lot of temporary lists -
George's version does it with the recursive calls to flatten, and Ron's
with the slicing and concatenating. How about a version which never
makes new lists, only appends the base list? We can use recursion to
root through the lists ...

Ok... How about a non-recursive flatten in place? ;-)

def flatten(seq):
i = 0
while i!=len(seq):
while isinstance(seq,list):
seq.__setslice__(i,i+1,seq)
i+=1
return seq

seq = [[1,2],[3],[],[4,[5,6]]]
print flatten(seq)

I think I'll be using the __setslice__ method more often.



And the test:
#--------------------------------

# Georges recursive flatten
init_a = """
def flatten(seq):
return reduce(_accum, seq, [])

def _accum(seq, x):
if isinstance(x,list):
seq.extend(flatten(x))
else:
seq.append(x)
return seq

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Ron's non-recursive
init_b = """
def flatten(seq):
s = []
while seq:
while isinstance(seq[0],list):
seq = seq[0]+seq[1:]
s.append(seq.pop(0))
return s

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Tom's recursive, no list copies made
init_c = """
def isiterable(x):
return hasattr(x, "__iter__") # close enough for government work

def visit(fn, x): # perhaps better called applytoall
if (isiterable(x)):
for y in x: visit(fn, y)
else:
fn(x)

def flatten(seq):
a = []
def appendtoa(x):
a.append(x)
visit(appendtoa, seq)
return a

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Devan' smallest recursive
init_d = """
def flatten(iterable):
if not hasattr(iterable, '__iter__'):
return [iterable]
return sum([flatten(element) for element in iterable],[])

seq = [[1,2],[3],[],[4,[5,6]]]
"""

# Ron's non-recursive flatten in place! Much faster too!
init_e = """
def flatten(seq):
i = 0
while i!=len(seq):
while isinstance(seq,list):
seq.__setslice__(i,i+1,seq)
i+=1
return seq

seq = [[1,2],[3],[],[4,[5,6]]]
"""

import timeit
t = timeit.Timer("flatten(seq)",init_a)
print 'recursive flatten:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_b)
print 'flatten in place-non recursive:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_c)
print 'recursive-no copies:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_d)
print 'smallest recursive:',t.timeit()

import timeit
t = timeit.Timer("flatten(seq)",init_e)
print 'non-recursive flatten in place without copies:',t.timeit()

#--------------------------------------------


The results on Python 2.3.5: (maybe someone can try it on 2.4)

recursive flatten: 23.6332723852
flatten in place-non recursive: 22.1817641628
recursive-no copies: 30.909762833
smallest recursive: 35.2678756658
non-recursive flatten in place without copies: 7.8551944451


A 300% improvement!!!

This shows the value of avoiding copies, recursion, and extra function
calls.

Cheers,
Ron Adam

 

[Ron Adam]

Ok... How about a non-recursive flatten in place? ;-)

def flatten(seq):
i = 0
while i!=len(seq):
while isinstance(seq,list):
seq.__setslice__(i,i+1,seq)
i+=1
return seq

seq = [[1,2],[3],[],[4,[5,6]]]
print flatten(seq)

I think I'll be using the __setslice__ method more often.

This is probably the more correct way to do it.

def flatten(seq):
i = 0
while i!=len(seq):
while isinstance(seq,list):
seq[i:i+1]=seq
i+=1
return seq

 

[Steven D'Aprano]

This is still a relevant distinction. One relevant point is that I am
perfectly free to use, say, the Spanish or Chinese word to describe
"module" or "function", but the keywords "def" and "import" will
remain the same.

No, that isn't relevant. That's just localisation. I'm also free to fork
Python and change the keywords.

[snip]

The "Python sense" is not arbitrary. There are very direct visual or
logical (i.e. INTUITIVE) connections between these words' *English*
meanings (not just mathematical, either) and their meanings in Python.

I had NEVER even heard the word "tuple" before learning Python. I spent
weeks mispelling it as "turple", and I finally had to look it up in a
dictionary to see if it was a real English word. Out of the four English
dictionaries in my house, none of them have the word.

Let's dump tuple from the language too, its just "a stupid name for a list
that can't change". Agreed?

[snip]

Similarly, "decorate" is 'make more attractive by adding ornament,
colour, etc.' In Python, a "decorator" applies a wrapper to a function
to provide it with some additional functionality.

Which is certainly NOT decoration, since the point of decoration is that
it is not functional! Plain bathroom tiles are functional. Decorating them
with leaves or flowers or patterns is not functional.

[snip]

Now, if you are armed ONLY with the English definition, you will
possibly run into some trouble, because the programming usage is a
*specialization* of the term -- we strictly take only *one* of the
English definitions to apply, and we narrow its meaning a bit.

Yes. Every specialization has its own jargon, and computer programming is
no different. One of the things new programmers have to learn is the
jargon.

[snip]

"lambda" has no such advantage. Here's the *entire* gcide definition:

Nonsense. All that means is that lambda in the programming sense is too
specialized to make it into most ordinary dictionaries. Just like tuple.

[snip]

Total BS. I knew the word "function" in it's English language sense,
probably by the time I was 6. I *know* my kids know it.

Okay, maybe my memories of being five are faulty.

But if not six, then five, or four, or three, or two. At _some_time_
function was entirely unknown to you, and you had to just learn it.

[snip]

If you're arguing that language is acquired rather than innate, you are
bludgeoning an obvious point. The point is that *jargon* should ideally
derive in a natural way from commonly-used language,

That's a bonus, sure. It is an important rule to follow, but not at the
expense of distorting the language:

t = immutable_list(L)
map(anonymous_function x: x+1, L)

versus:

t = tuple(L)
map(lambda x: x+1, L)

if we want it to be
easy to acquire for people who don't learn programming between the ages
of 1 and 5 as we learn our native languages. Even in the 21st century,
I think this includes just about all of us. ;-)

If they can't memorize one or two things, they aren't going to be much
good at programming no matter how easy the language is to use.

Ah, but that's useful. "Strings" AREN'T "multiple lines of text" in the
computer's memory, are they? '\n' is just another bead. The "multiple
lines" is a representation, or way of laying out the beads. Very useful
distinction, and immediately driven by the choice of analogy.

Who cares about the implementation details of how the bytes are laid out
in the computer's memory? Unless you are programming in a low level
language like C or assembly, this is entirely irrelevant. You have
characters laid out along lines, and lines laid out in a second dimension.
The natural way to work with text is something like this:

for line in text:
for word in line: # or character
do_something()

[snip]

Then it is clearly *not you* who should be served by the naming scheme.
Anyone so deeply trained and experienced should be expected to adapt,
you have the wherewithall to do so. It is the new user for whom the
clarity of the jargon is so important.

Personally, I find the term "anonymous function" to be a whole lot
clearer than "lambda" or "lambda function". Indeed, if asked what
"lambda" means, my reply is it's a "stupid name for an anonymous
function", and if my listener is less savvy "for a function that doesn't
have a name, because you only use it once".

And any half-way experienced Python programmer will say, "What are you
talking about?"

add_one = lambda x: x+1

Yes, I know that the name "add_one" is not the same as the name for a
function when you use def, but the function still has a name. The
difference might be an important difference, but it is not one you care
about unless you are doing introspection.

Having said that, I too will miss the *concept* of an anonymous
function, although I wouldn't mind at all if its name changed, or if it
were somehow integrated into the "def" keyword's usage.

Def would be short for ... defend? defile? defer? defame? default? deflect?

There's always *something* to learn. Why def instead of define? Because
"easy to write" beats "instantly obvious to a beginner", if the word is
used all the time and is easy to memorize.

Using backticks
or some other syntax delimiter also sounds promising,

Ew, perl :-(

 

[Tom Anderson]

Ok... How about a non-recursive flatten in place? ;-)

How about, er, oh, i give up.

def flatten(seq):
i = 0
while i!=len(seq):
while isinstance(seq,list):
seq.__setslice__(i,i+1,seq)
i+=1
return seq

seq = [[1,2],[3],[],[4,[5,6]]]
print flatten(seq)

I think I'll be using the __setslice__ method more often.

Um, can't you just do slice assignment? Make that line:

seq[i:i+1] = seq

And the test:

Stupendous and timely work!

The results on Python 2.3.5: (maybe someone can try it on 2.4)

recursive flatten: 23.6332723852
flatten in place-non recursive: 22.1817641628
recursive-no copies: 30.909762833
smallest recursive: 35.2678756658
non-recursive flatten in place without copies: 7.8551944451
GAAAAH!

A 300% improvement!!!

This shows the value of avoiding copies, recursion, and extra function
calls.

Specifically, it shows the value of avoiding extra function calls, since
my zerocopy version is slower than the copy-happy single-function
versions.

Also, there are some differences between the functions which constitute
potential hillocks on the playing field - i test flattenability by looking
for an __iter__ method, whereas other implementations mostly ask
"instanceof list?" (less general, and less in the spirit of duck typing,
IMNERHO). I'd argue that my decomposition into functions is this sort of
difference, too - a matter of style (good style!), not algorithm. So,
levelling those differences, and throwing in my non-recursive zerocopy
foolery, here's my take on it ...

# ----

# here be a quick reimplementation of timeit to time function objects
# no exec for me no siree bob
# all you need to know is that timeit(fn) gives you time taken to run fn

import sys
import time

TIMERS = {
"win32": time.clock
}

timer = TIMERS.get(sys.platform, time.time)

def timeit(fn, n=None):
if (n == None):
t = 0.1
n = 1
while (t < 1.0):
n = max(int((n * min((1.0 / t), 10))), (n + 1))
t = _timeit(fn, n)
else:
t = _timeit(fn, n)
return t / n

def _timeit(fn, n):
it = xrange(n)
t0 = timer()
for i in it:
fn()
t1 = timer()
return float((t1 - t0))

# there is real code now
# i've rewritten the functions to use uniform variable names
# and to use isiterable

def isiterable(obj):
return hasattr(obj, "__iter__")

def georges_recursive_flatten(seq):
return reduce(_accum, seq, [])

def _accum(a, item):
if isiterable(item):
a.extend(georges_recursive_flatten(item))
else:
a.append(item)
return a

def rons_nonrecursive_flatten(seq):
a = []
while seq:
while isiterable(seq[0]):
seq = seq[0] + seq[1:]
a.append(seq.pop(0))
return a

def toms_recursive_zerocopy_flatten(seq, a=[]):
if (isiterable(seq)):
for item in seq:
toms_recursive_zerocopy_flatten(item, a)
else:
a.append(seq)
return a

def toms_iterative_zerocopy_flatten(seq):
stack = [None]
cur = iter(seq)
a = []
while (cur != None):
try:
item = cur.next()
if (isiterable(item)):
stack.append(cur)
cur = iter(item)
else:
a.append(item)
except StopIteration:
cur = stack.pop()
return a

def devans_smallest_recursive_flatten(seq):
if (isiterable(seq)):
return sum([devans_smallest_recursive_flatten(item) for item in seq], [])
else:
return [seq]

def rons_nonrecursive_inplace_flatten(seq):
i = 0
while (i != len(seq)):
while (isiterable(seq)):
seq[ii + 1)] = seq # setslice takes iterators!
i = i + 1
return seq

flattens = [
georges_recursive_flatten,
rons_nonrecursive_flatten,
toms_recursive_zerocopy_flatten,
toms_iterative_zerocopy_flatten,
devans_smallest_recursive_flatten,
rons_nonrecursive_inplace_flatten
]

seq = [[1,2],[3],[],[4,[5,6]]]

def timeflatten(flatten):
return timeit(lambda: flatten(seq))

def funcname(fn):
return fn.func_name

print zip(map(funcname, flattens), map(timeflatten, flattens))

# ----

The output (in python 2.3 on a 1.5 GHz G4 pbook with OS X 10.3) is:

[
('georges_recursive_flatten', 0.00015331475192276888),
('rons_nonrecursive_flatten', 0.00015447115513356376),
('toms_recursive_zerocopy_flatten', 0.00012239551614106925),
('toms_iterative_zerocopy_flatten', 0.00035910996630353429),
('devans_smallest_recursive_flatten', 0.00019606360118084218),
('rons_nonrecursive_inplace_flatten', 5.8524826144294404e-05)
]

So, my zerocopy flatten is, after all, faster than George, you and Devan's
copy-happy versions, although not by much, my iterative version is much,
much slower, and the winner is still your in-place flatten, which beats my
not-too-bad 122 microseconds with a scorching 58!

I guess setslice is a lot faster than i thought. How are python lists
implemented? Presumably not as straightforward arrays, where inserting a
bunch of items at the head would mean moving everything else in the list
along?

We really ought to do this benchmark with a bigger list as input - a few
thousand elements, at least. But that would mean writing a function to
generate random nested lists, and that would mean specifying parameters
for the geometry of its nestedness, and that would mean exploring the
dependence of the performance of each flatten on each parameter, and that
would mean staying up until one, so i'm not going to do that.

tom

 

[Steven D'Aprano]

And besides, "def" isn't a "magic" word... it's an abreviation for
"define"...

Really? I thought it was an abbreviation for "definition". As in,
"definition of MyFunc is..."

I hope that any student who didn't understand a word as
common as "define" wouldn't have graduated from our school.

How about tuple?

 

[Steven Bethard]

I can't believe that anybody with any computer science
background doesn't know it.

Perhaps this reflects on the quality of education in the United States
but I managed to get a BS in Computer Science at the University of
Arizona without ever seeing the word lambda (in the programming
languages sense).

However, I only took one class in programming languages, and it was more
of a survey class than a theory class. When I did take a theory class,
here at University of Colorado at Boulder, they did, of course, cover
lambda calculus. But there was at least a year or two in which I would
have considered myself somebody "with any computer science background"
who wasn't familiar with lambda.

OTOH, I fully agree with Peter Hansen: "Really, the name is such a
trivial, unimportant part of this whole thing that it's hardly worth
discussing."

STeVe

 

[George Sakkis]

On Tue, 05 Jul 2005 09:46:41 -0500, Terry Hancock wrote: [snip]

Having said that, I too will miss the *concept* of an anonymous
function, although I wouldn't mind at all if its name changed, or if it
were somehow integrated into the "def" keyword's usage.

Def would be short for ... defend? defile? defer? defame? default? deflect?

There's always *something* to learn. Why def instead of define? Because
"easy to write" beats "instantly obvious to a beginner", if the word is
used all the time and is easy to memorize.

Still it's hard to explain why four specific python keywords - def,
del, exec and elif - were chosen to be abbreviated, while all the rest
are full words (http://docs.python.org/ref/keywords.html). "Ease of
typing" is a joke for an excuse; "finally" is longer than
"define","delete" and equally long to "execute" and "else if" (the
latter has the even more serious flaw of going against TOOWTDI and in
this case practicallity hardly beats purity IMO). In any case, python
was never about minimizing keystrokes; theres another language that
strives for this <wink>.

So, who would object the full-word versions for python 3K ?
def -> define
del -> delete
exec -> execute
elif -> else if

George

 

[Terry Reedy]

I guess setslice is a lot faster than i thought.

Nope, the example is too short to be meaningful.

How are python lists
implemented? Presumably not as straightforward arrays, where inserting a
bunch of items at the head would mean moving everything else in the list
along?

They *are* extensible arrays, and insertion *does* mean exactly that --
moving everything else along -- although CPython probably does it with C
memcopy(). So the littly puny 'test' example with about 20 total elements
is testing overhead, not large-list behavior. So you are right, *much*
longer lists are needed. You could start, for example, with a list of 1000
lists of 1000 elements (all 0 would be fine). Or maybe 100 of 100 of 100.
For that, I would start with something that appended and extended the
result list. Or try writing a generator iflatten that yielded elements in
order:
def flatten(iterable): return list(iflatten(iterable))
which pushes appending down into the C code of list().

Terry J. Reedy

 

[Terry Reedy]

OTOH, I fully agree with Peter Hansen: "Really, the name is such a
trivial, unimportant part of this whole thing that it's hardly worth
discussing."

From a certain viewpoint, I would agree. Yet, the word 'lambda' *is* the

center of most of the fuss. For beginners, it is a minor issue: learn it
and move on. But for some functionalists, it is a major issue. They
'know' that lambda means 'expressionized anonymous function'. And in
lambda calculus, it is the main actor. But in Python, lambda only means
anonymous trivial function. It is only an expressionized convenience
abbreviation for an important but small subset of possible functions. So
for years, such knowledgeable people have called for and proposed various
syntaxes for 'proper lambdas' or 'true lambdas', saying pretty clearly that
what Python has is improper or false. Would there have been so much fuss
if the keyword had been 'fun' and the word 'lambda' had never appeared in
the Python docs? I strongly doubt it.

I also suspect that the years of fuss over Python's lambda being what it is
rather that what it is 'supposed' to be (and is in other languages) but is
not, has encourage Guido to consider just getting rid of it. I personally
might prefer keeping the feature but using a different keyword.

Terry J. Reedy

 

[Terry Reedy]

Still it's hard to explain why four specific python keywords - def,
del, exec and elif - were chosen to be abbreviated,

Precedence in other languages and CS usage?

So, who would object the full-word versions for python 3K ?
def -> define
del -> delete
exec -> execute

These three I might prefer to keep.

elif -> else if

This one I dislike and would prefer to write out. I never liked it in
whatever else language I first encountered it and still don't.

Terry J. Reedy

 

[Ron Adam]

We really ought to do this benchmark with a bigger list as input - a few
thousand elements, at least. But that would mean writing a function to
generate random nested lists, and that would mean specifying parameters
for the geometry of its nestedness, and that would mean exploring the
dependence of the performance of each flatten on each parameter, and
that would mean staying up until one, so i'm not going to do that.

tom

Without getting to picky, would this do?

import random
import time
random.seed(time.time())

def rand_depth_sequence(seq):
for n in range(len(seq)):
start = random.randint(0,len(seq)-2)
end = random.randint(start,start+3)
seq[start:end]=[seq[start:end]]
return seq

seq = rand_depth_seq(range(100))
print seq

[[[[[0, 1], 2, [3, [4, 5, 6]]], [7], [8, [[9, [], 10]]]], [11, [12]],
[[[]]]], [[], [13, 14, 15]], [[[16, 17]]], [18], [[[19], 20, [[21, 22,
[23]], [[24]]]], 25, 26], [], [27, 28], [], 29, [], [30, [31, 32, 33]],
[34], [[35]], 36, [[37, 38, 39], [[40, 41], [[42]]]], [43, 44], 45, 46,
[47, []], [[[48, 49], [50], [51]], 52], [[[53], [54, 55, [56, 57, 58]],
[]], [], []], [[59, 60, 61]], 62, [[63]], [], [64], [[[65]]], [[[66, 67,
68], [69, 70, [71, 72]], [[73, 74], [75, 76]]], [77, 78]], [], 79, 80,
[[81], []], 82, [[[83, [[], 84], [85]], 86, [[87, 88]]], [[[89], 90,
91], [92, [93], [94, 95, 96]]]], [97, [98, 99]]]