[Tutor] how to flatten and lump lists

[Daniel Yoo]

First, let's start off by showing what we want flatten() to do.  We'd
expect that:

    flatten([1, 2, 3, 4]),
    flatten([ [1], 2, [3, [4]] ]), and
    flatten([ [1], [2], [3], [4] ])

to all return the list [1, 2, 3, 4].

One simple way to solve this problem is to use recursion --- if we have
some list L that we'd like to flatten, we can pretend that flatten() will
work on a smaller version of a list.

So, a partial definition of flatten() would be:

###
def flatten(L):
    return flatten(L[0]) + flatten(L[1:])
###

What this means is, let's flatten the first element of our list L, and
let's flatten the rest of L.  Finally, concatenate the lists together, and
we'll be done.

All we need to do now is tell Python our "base cases" --- stuff that
should be so obvious that we don't need to call flatten() recursively.  
Here's the first:

    if L is not a list, return a list containing L.

and we can write this in Python as:

    if type(L) != type([]): return [L]

Another obvious case is trying to flatten the empty list --- when we say:

    flatten([])

we should just get back the empty list.

Putting everything together, here's the complete version of the flatten()
function:

###
def flatten(L):
    if type(L) != type([]): return [L]
    if L == []: return L
    return flatten(L[0]) + flatten(L[1:])
###


Let's test it out.

###
>>> flatten([1, 2, 3, 4, 5])
[1, 2, 3, 4, 5]
>>> flatten([1, [2, 3, [4], [5]]]) 
[1, 2, 3, 4, 5]
>>> flatten([[1], [2], [3], [4], [5]])
[1, 2, 3, 4, 5]
###

Hope this helps!


On Tue, 2 Jan 2001, kevin parks wrote:
> 
> Sure. Maybe i'll learn something from it. Thanks!
> 
> --
> 
> On Mon, 1 Jan 2001 19:31:51   
>  Daniel Yoo wrote:
> >On Mon, 1 Jan 2001, kevin parks wrote:
> >
> >> I got it! just so the tutors here know there is no need to reply. i
> >> got the usual entertaining and informative lesson from Mr. Peters.
> >> Still absorbing the nuances of his answer which is son-like (jp:zen).
> >
> >Are you still interested in the list flattening code?  If you'd like, I
> >can post it to the tutor list.