Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #7012 > unrolled thread

Lambda question

Back to article view | Back to comp.lang.python

Contents

  Lambda question <jyoung79@kc.rr.com> - 2011-06-04 17:46 +0000
    Re: Lambda question Mel <mwilson@the-wire.com> - 2011-06-04 14:21 -0400
    Re: Lambda question Alain Ketterlin <alain@dpt-info.u-strasbg.fr> - 2011-06-05 11:31 +0200
      Re: Lambda question Terry Reedy <tjreedy@udel.edu> - 2011-06-05 14:33 -0400
        Re: Lambda question rusi <rustompmody@gmail.com> - 2011-06-06 10:29 -0700
          Re: Lambda question Terry Reedy <tjreedy@udel.edu> - 2011-06-06 21:56 -0400

#7012 — Lambda question

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 

[toc] | [next] | [standalone]

#7014

jyoung79@kc.rr.com wrote:

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

[toc] | [prev] | [next] | [standalone]

#7039

<jyoung79@kc.rr.com> writes:

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

[toc] | [prev] | [next] | [standalone]

#7054

On 6/5/2011 5:31 AM, Alain Ketterlin wrote:
> <jyoung79@kc.rr.com>  writes:
>
>>>>> 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+]

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#7097

On Jun 5, 11:33 pm, Terry Reedy <tjre...@udel.edu> wrote:
> On 6/5/2011 5:31 AM, Alain Ketterlin wrote:
>
> > <jyoun...@kc.rr.com>  writes:
>
> >>>>> 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?

[toc] | [prev] | [next] | [standalone]

#7126

On 6/6/2011 1:29 PM, rusi wrote:
> On Jun 5, 11:33 pm, Terry Reedy<tjre...@udel.edu>  wrote:

>> 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?

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.)

-- 
Terry Jan Reedy

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web