Lambda question
jyou...@kc.rr.com
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
Chris Angelico
> 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']
First, the easy bit. 'dude'[3:] is a slice operation on the string;
same with 'dude'[:3]. Imagine the gaps between the letters as being
numbered from zero:
| d | u | d | e |
0 1 2 3 4
'dude'[3:] means "take the string 'dude', start at position 3, and go
to the end of the string" - so that's just the letter "e". Similarly,
'dude'[:3] means "take the string 'dude', start at the beginning, and
go to position 3" - so that's "dud".
Here's a version of that function, redone in a slightly less compact form:
def strsplit(string,n,acc=[]):
if string:
return strsplit(string[n:],n,acc+[string[:n]])
else:
return acc
Yes, it's recursive. In each iteration, until the string is empty, it
takes the first n characters and puts them in the accumulator list,
and then trims those n off and leaves them in the string. Here's a
non-recursive version:
def strsplit(string,n):
acc=[]
while string:
acc.append(string[:n])
string=string[n:]
return acc
This might make it a bit clearer what it does. The accumulator
collects ("accumulates") short strings, the string gets progressively
snipped, and once the string is empty, it evaluates as False and
terminates the loop.
Python doesn't seem to have an inbuilt function to divide strings in
this way. At least, I can't find it (except the special case where n
is 1, which is simply 'list(string)'). Pike allows you to use the
division operator: "Hello, world!"/3 is an array of 3-character
strings. If there's anything in Python to do the same, I'm sure
someone else will point it out.
Hope that helps!
Chris Angelico
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.
Ian Kelly
> Python doesn't seem to have an inbuilt function to divide strings in
> this way. At least, I can't find it (except the special case where n
> is 1, which is simply 'list(string)'). Pike allows you to use the
> division operator: "Hello, world!"/3 is an array of 3-character
> strings. If there's anything in Python to do the same, I'm sure
> someone else will point it out.
Not strictly built-in, but using the "grouper" recipe from the
itertools docs, one could do this:
def strsection(x, n):
return map(''.join, grouper(n, x, ''))
Cheers,
Ian
Vito 'ZeD' De Tullio
> I was surfing around looking for a way to split a list into equal
> sections.
non-recursive, same-unreadeable (worse?) one liner alternative:
def chunks(s, j):
return [''.join(filter(None,c))for c in map(None,*(s[i::j]for i in
range(j)))]
--
By ZeD
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
> <jyou...@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
jyou...@kc.rr.com
> 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
Thank you all very much for this incredible help! The original code
now makes sense, and I was thrilled to see better and more efficient
ways of doing this. Thanks for taking the time to share your
thoughts as well as the excellent detail everyone shared… I really
appreciate it!
Jay
Terry Reedy
>>>>>> 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):
[I added back the last 'n' that got deleted somehow]
> Thank you all very much for this incredible help! The original code
> now makes sense, and I was thrilled to see better and more efficient
> ways of doing this. Thanks for taking the time to share your
> thoughts as well as the excellent detail everyone shared… I really
> appreciate it!
You are welcome.
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.) Test cases help test the
definition statement as well as the yet-to-be-written code. They also
make re-factoring much safer. I think test cases should start with null
inputs. For this function:
for inn,out in (
(('',1), []), # no input, no output
(('abc',0), []), # definition unclear, could be error
(('abc',1), ['a','b','c']),
(('abcd',2), ['ab','cd']),
(('abcde',2), ['ab', 'cd', 'e']), # could change this
):
assert list(group(*inn)) == out, (inn,out)
This fails with
ValueError: range() arg 3 must not be zero
I will let you think about and try out what the original code 'f=../
does with n=0. It is not good. A third problem with lambda expressions
is no test for bad inputs. They were added to Python for situations
where one needs a function as an argument and and the return expression
is self-explanatory, clearly correct, and safe for any inputs it could
get in the context it is passed into. For example, lambda x: 2*x.
This works:
def group(seq, n):
'Yield from seq successive disjoint slices of length n & the remainder'
if n<=0: raise ValueError('group size must be positive')
for i in range(0,len(seq), n):
yield seq[i:i+n]
for inn,out in (
(('',1), []), # no input, no output
#(('abc',0), ValueError), # group size positive
(('abc',1), ['a','b','c']),
(('abcd',2), ['ab','cd']),
(('abcde',2), ['ab', 'cd', 'e']), # could change this
):
assert list(group(*inn)) == out, (inn,out)
I have written a function test function that I will post or upload to
PyPI sometime. It accepts i/o pairs with error 'outputs', like the one
commented out above.
--
Terry Jan Reedy
rusi
> On 6/5/2011 5:31 AM, Alain Ketterlin wrote:
>
>
> >>>>> 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']
>
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?
Steven D'Aprano
> 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.)
For any non-trivial function, I usually start by writing the
documentation (a docstring and doctests) first. How else do you know what
the function is supposed to do if you don't have it documented?
By writing the documentation and examples before the code, I often
discover that the API I first thought of was rubbish :)
--
Steven
Ben Finney
> On Mon, 06 Jun 2011 12:52:31 -0400, Terry Reedy 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.)
>
> For any non-trivial function, I usually start by writing the
> documentation (a docstring and doctests) first. How else do you know
> what the function is supposed to do if you don't have it documented?
By trying to use it. At least, that's my approach: figure out what I
want the function to do by pretending it already exists, and write some
code that expects it to work.
Sometimes that code is a test case (in which case I'm doing test-first
development). Other times I'm not sure what I *want* the function to do
yet, so I'm also experimenting with what the interface should be (in
which case I'm doing something closer to a “spike implementation”).
All of that also stops me from writing the function until I can think of
a descriptive name for the function, and a docstring synopsis: the first
line of the docstring, a self-contained sentence saying what the
function is for. The synopsis should be exactly one short line; see PEP
257.
Once I know the function signature (parameters and return value), then I
write the docstring body.
> By writing the documentation and examples before the code, I often
> discover that the API I first thought of was rubbish :)
Yep. That's also a big benefit of designing code by pretending it
exists, I find.
Fred Brooks tells us that we should plan from the beginning to throw one
away; because we will, anyhow. You and I seem to have ways to invest as
little as possible in the first design before throwing it away :-)
--
\ “Are you pondering what I'm pondering?” “Umm, I think so, Don |
`\ Cerebro, but, umm, why would Sophia Loren do a musical?” |
_o__) —_Pinky and The Brain_ |
Ben Finney
harrismh777
> For any non-trivial function, I usually start by writing the
> documentation (a docstring and doctests) first. How else do you know what
> the function is supposed to do if you don't have it documented?
Yes. In my early years I was no different than any other hacker in terms
of documenting last if at all... but having flown around the sun a few
more times I've realized that good clear doc 'before' the code actually
helps me write good clean code. If I implement what I've documented then
I'm less likely to miss something in the doc, and more likely to have
fewer bugs... this has played itself out many times for me.
kind regards,
m harris
Terry Reedy
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
Terry Reedy
> def group(seq, n):
> 'Yield from seq successive disjoint slices of length n & the remainder'
> if n<=0: raise ValueError('group size must be positive')
> for i in range(0,len(seq), n):
> yield seq[i:i+n]
>
> for inn,out in (
> (('',1), []), # no input, no output
> #(('abc',0), ValueError), # group size positive
> (('abc',1), ['a','b','c']),
> (('abcd',2), ['ab','cd']),
> (('abcde',2), ['ab', 'cd', 'e']), # could change this
> ):
> assert list(group(*inn)) == out, (inn,out)
I forgot to mention that any function that takes a 'sequence' as input
should be tested with both strings and non-strings. I learned this when
a function tested with one failed mysteriously with the other. Strings
are unique in that indexing returns a slice (and hence a string) rather
than a separate class of item. It this case, there is no indexing and no
use of class to create new items. However, adding a couple of lines like
(((),1), []),
(((1,2,3,4),2), [(1,2), (3,4)]),
to the test sequence checks the current code and guards against future
changes.
--
Terry Jan Reedy