Lambda question

[Alain Ketterlin]

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