Lambda question

[Guest]

I was surfing around looking for a way to split a list into equal sections. I
came upon this algorithm:

f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc
f("Hallo Welt", 3)

['Hal', 'lo ', 'Wel', 't']

http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-s
ized-chunks-in-python/312644

It doesn't work with a huge list, but looks like it could be handy in certain
circumstances. I'm trying to understand this code, but am totally lost. I
know a little bit about lambda, as well as the ternary operator, but how
does this part work:

f('dude'[3:], 3, []+[('dude'[:3])])

['dud', 'e']

Is that some sort of function call, or something else? I'm guessing it works
recursively?

Just curious if anyone could explain how this works or maybe share a link
to a website that might explain this?

Thanks.

Jay

 

[Mel]

I was surfing around looking for a way to split a list into equal
sections. I came upon this algorithm:

f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc
f("Hallo Welt", 3)

['Hal', 'lo ', 'Wel', 't']

http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into- evenly-s
ized-chunks-in-python/312644

It doesn't work with a huge list, but looks like it could be handy in
certain
circumstances. I'm trying to understand this code, but am totally lost.
I know a little bit about lambda, as well as the ternary operator, but how
does this part work:

f('dude'[3:], 3, []+[('dude'[:3])])

['dud', 'e']

Is that some sort of function call, or something else? I'm guessing it
works recursively?

Yeah, recursive.

f('dude', 3)

evaluates to

f('e', 3, []+['dud']) if 'dude' else []

which evaluates to

f('', 3, []+['dud']+['e']) if 'e' else []+['dud']

which evaluates to

[]+['dud']+['e']

because the if...else finally takes the second branch since the x value is
now an empty string.

I've left the list additions undone .. tracing the actual data objects would
show plain lists. One of the disadvantages of lambdas is that you can't
stick trace printouts into them to clarify what's happening. Rewriting the
thing as a plain def function would be instructive.

Mel.

 

[Alain Ketterlin]

f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc
f("Hallo Welt", 3)

['Hal', 'lo ', 'Wel', 't']

http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-s
ized-chunks-in-python/312644

It doesn't work with a huge list, but looks like it could be handy in certain
circumstances. I'm trying to understand this code, but am totally lost.

With such dense code, it is a good idea to rewrite the code using some
more familiar (but equivalent) constructions. In that case:

f = <a function that can be called with parameters> x, n, acc=[]:
<if> x <is not empty>
<result-is> f(x[n:], n, acc+[(x[:n])])
<else>
<result-is> acc

I've made one major change here: the "<value-true> if <condition> else
<value-false>" *expression* has been changed to an "if-the-else"
*instruction*. I use <if> etc. to emphasize the fact that it is somehow
special, but it should run as the usual if-then-else construct. This
transformation is correct here only because 1) it has both "then" and
"else" branches, and 2) both branches evaluate an *expression* (i.e.,
they are of the form <result-is> ..., and nothing else).

What now remains is to understand the logic of the computation. It is a
recursive definition of f, so it has a base case and a recursion case.
Note that the base case (my <else> branch) does nothing except returning
what it gets as the third parameter. Wow, this code is in some sort able
to "anticipate": in some cases, f is called with a pre-cooked result
(it's often called an accumulator: some calling function has accumulated
data for f to use). Since f is calling f, it means that, even when f has
to call itself, it can still make some progress towards the final
result.

Now look at the recursive call: when we are in a situation where we
cannot make a final decision, we simply chop of (at most) n items
from the start of input list. If we do this, we're left with a (possibly
empty) list "tail" (x[n:]), and we've found a part of the result
(x[:n]).

How does the whole thing work. Imagine a sequence of calls to f, each
one contributing some part of the result (a n-letter chunk):

... -> f -> f -> f -> ... -> f (done)

In this chain of recursive calls, each call to f except the last
contributes one chunk, "accumulates" it in a partial result, and
computes the work that "remains" for the subsequent calls. The last call
"knows" it is the last, and simply acknowledges the fact that all
previous calls have done all the work. The acumulator gets filled along
this chain.

There are a few details that we need to make sure of:

1) what if the initial list has a lentgh that isn't a multiple of n?
This is taken care of by python's slicing (x[:n] will only go as far as
possible, maybe less than n items; and x[n:] will be empty if x has less
than n elements)

2) Where does the accumulator come from? The first call uses the default
value declared in the lambda parameters. Calling f("abcd",2) is like
calling f("abcd",2,[]).

We could have done this differently: for instance

f = lambda x,n: [x[:n]] + f(x[n:],n) if x else []

This has no accumulator, because the result is computed "the other way
round": subsequent calls are left with the tail of the list, return the
result, and then we put the starting chunk in front of the result. No
need for an accumulator, the result is built when "coming back" from
recursive calls (i.e., from right to left in the chain of calls pictured
as above). Somewhat surprisingly, this is usually less efficient than
the one you show. The reason is that here there is some work to do
before the recursive call (extracting a chunk) *and* after the call
(pasting together the chunk with the result coming back from the
recursive call). Therefore, all intermediate results have to be kept for
intermediate calls. This doesn't happen in your version: an intermediate
call was updating a "global" partial result (acc) and that was it. (This
remark has a lot of technical implications.)

-- Alain.

P/S: wikipedia has some info on "recursion" to start with if you want lo
learn more.

 

[Terry Reedy]

f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc

f=lambda ... statements are inferior for practical purposes to the
equivalent def f statements because the resulting object is missing a
useful name attribute and a docstring. f=lambda is only useful for
saving a couple of characters, and the above has many unneeded spaces

f("Hallo Welt", 3)

['Hal', 'lo ', 'Wel', 't']

http://stackoverflow.com/questions/312443/how-do-you-split-a-list-into-evenly-s
ized-chunks-in-python/312644

It doesn't work with a huge list, but looks like it could be handy in certain
circumstances. I'm trying to understand this code, but am totally lost.

With such dense code, it is a good idea to rewrite the code using some
more familiar (but equivalent) constructions. In that case:

f =<a function that can be called with parameters> x, n, acc=[]:
<if> x<is not empty>
<result-is> f(x[n:], n, acc+[(x[:n])])
<else>
<result-is> acc

Yes, the following is much easier to read:

def f(x, n, acc=[]):
if x:
return f(x[n:], n, acc + [x[:n]])
else:
return acc

And it can be easily translated to:

def f(x,n):
acc = []
while x:
acc.append(x[:n]) # grab first n chars
x = x[n:] # before clipping x
return acc

The repeated rebinding of x is the obvious problem. Returning a list
instead of yielding chunks is unnecessary and a problem with large
inputs. Solving the latter simplies the code to:

def group(x,n):
while x:
yield x[:n] # grab first n chars
x = x[n:] # before clipping x

print(list(group('abcdefghik',3)))
# ['abc', 'def', 'ghi', 'k']

Now we can think about slicing chunks out of the sequence by moving the
slice index instead of slicing and rebinding the sequence.

def f(x,n):
for i in range(0,len(x),n):
yield x[i:i+n]

This is *more* useful that the original f= above and has several *fewer*
typed characters, even is not all on one line (and decent editor add the
indents automatically):

def f(x,n): for i in range(0,len(x),n): yield x[i:i+n]
f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc

Packing tail recursion into one line is bad for both understanding and
refactoring. Use better names and a docstring gives

def group(seq, n):
'Yield from seq successive disjoint slices of length n plus the
remainder'
for i in range(0,len(seq), n):
yield seq[i:i+]

 

[rusi]

f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc

f=lambda ... statements are inferior for practical purposes to the
equivalent def f statements because the resulting object is missing a
useful name attribute and a docstring. f=lambda is only useful for
saving a couple of characters, and the above has many unneeded spaces

f("Hallo Welt", 3)
['Hal', 'lo ', 'Wel', 't']
http://stackoverflow.com/questions/312443/how-do-you-split-a-list-int....
ized-chunks-in-python/312644
It doesn't work with a huge list, but looks like it could be handy in certain
circumstances.  I'm trying to understand this code, but am totally lost.

With such dense code, it is a good idea to rewrite the code using some
more familiar (but equivalent) constructions. In that case:

f =<a function that can be called with parameters>  x, n, acc=[]:
       <if>  x<is not empty>
         <result-is>  f(x[n:], n, acc+[(x[:n])])
       <else>
         <result-is>  acc

Yes, the following is much easier to read:

def f(x, n, acc=[]):
   if x:
     return f(x[n:], n, acc + [x[:n]])
   else:
     return acc

And it can be easily translated to:

def f(x,n):
   acc = []
   while x:
     acc.append(x[:n])  # grab first n chars
     x = x[n:]          # before clipping x
   return acc

The repeated rebinding of x is the obvious problem. Returning a list
instead of yielding chunks is unnecessary and a problem with large
inputs. Solving the latter simplies the code to:

def group(x,n):
   while x:
     yield x[:n]  # grab first n chars
     x = x[n:]    # before clipping x

print(list(group('abcdefghik',3)))
# ['abc', 'def', 'ghi', 'k']

Now we can think about slicing chunks out of the sequence by moving the
slice index instead of slicing and rebinding the sequence.

def f(x,n):
     for i in range(0,len(x),n):
         yield x[i:i+n]

This is *more* useful that the original f= above and has several *fewer*
typed characters, even is not all on one line (and decent editor add the
indents automatically):


def f(x,n): for i in range(0,len(x),n): yield x[i:i+n]
f = lambda x, n, acc=[]: f(x[n:], n, acc+[(x[:n])]) if x else acc

Well here is a quite-readable one-liner
def f(x,n): return (x[i:i+n] for i in range(0,len(x),n))

which if one is in character-lessening-spree mode can be written:

f=lambda x,n: (x[i:i+n] for i in range(0,len(x),n))

Let me add something not said much here about designing functions: start
with both a clear and succinct definition *and* test cases. (I only
started writing tests first a year ago or so.)

I am still one year in the future :-;
Which framework do you recommend? Nose? test.py?

 

[Terry Reedy]

I am still one year in the future :-;
Which framework do you recommend? Nose? test.py?

As I explained in a followup post, I am currently using a custom
function test function that accepts i/o pairs with exception classes as
'outputs'. It was inspired by test.py, but that is both overkill and an
unwanted external dependency for my current project. I also wrote and
use an iterator test function and a specialized iterator test function
for iterators that return sequences. (For better error reporting, the
latter tests items within each sequence rather than each sequence as a
whole. This is especially helpful when the items are themselves
collections, as in some combinatorial iterators.)