3

I am trying following recursive function to flatten sent list which may contain sublist items: 

def myflatten(slist, outlist=[]):
    for sl in slist:
        if type(sl) == list:    
            outlist.append(myflatten(sl, outlist))
        else: 
            outlist.append(sl)
    return outlist

print("myflatten list=", myflatten([1,[5,6,7],3,4,[7,8,9]]))

Output:

myflatten list= [1, 5, 6, 7, [...], 3, 4, 7, 8, 9, [...]]

Why am I getting [...] for every sublist and how can I avoid getting this? Thanks for your help.

rnso
  • 23,686
  • 25
  • 112
  • 234
  • 2
    `[...]` indicates the list contains itself – turbulencetoo Nov 30 '17 at 17:23
  • I think the problem is that you're updating the `default` reference for `outlist`. For instance, if you call `myflatten([1])`, and then call `myflatten([2])`, you'll get `[1, 2]` – Matias Cicero Nov 30 '17 at 17:23
  • 1
    This isn't the cause of your problem, but watch out for the [Default mutable gotcha](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument) in your function definition there. Even if you get your code working, it might produce surprising results if you call it more than once. – Kevin Nov 30 '17 at 17:25
  • @turbulencetoo Interesting! Hadn't seen that before, learn something new everyday! – Joe Iddon Nov 30 '17 at 17:26
  • @Kevin Actually, I think *it is* the cause of the problem. This is a recursive call. – Matias Cicero Nov 30 '17 at 17:26
  • @MatiasCicero, The problem would still occur even if he deleted the default argument and instead required an explicit reference. [Example](https://ideone.com/qstXH9) – Kevin Nov 30 '17 at 17:29

4 Answers4

2

Existing answers provide good explanations to why the [...] self-reference occurs, but their suggested revisions to the code don't do anything to address the default mutable argument gotcha that's waiting to bite you.

Here's a solution that doesn't require an outlist argument:

def myflatten(slist):
    outlist = []
    for sl in slist:
        if isinstance(sl, list):    
            outlist.extend(myflatten(sl))
        else: 
            outlist.append(sl)
    return outlist

print("myflatten list=", myflatten([1,[5,6,7],3,4,[7,8,9]]))
Kevin
  • 74,910
  • 12
  • 133
  • 166
  • Yes, it works perfectly. `extend` is a useful function. – rnso Nov 30 '17 at 17:37
  • Keeping a blank `accumulator` as an argument is common in Scheme/Racket/Lisp-derived languages (as in https://stackoverflow.com/questions/29425944/racket-accumulator-list-function ) – rnso Nov 30 '17 at 18:17
1

The problem is that myflatten is returning a list. So when you append the results of myflatten to the outlist it is appending a list. Try setting outlist equal to the result of myflatten:

def myflatten(slist, outlist=[]):
    for sl in slist:
        if type(sl) == list:    
            outlist = myflatten(sl, outlist) #HERE IS THE CHANGE
        else: 
            outlist.append(sl)
    return outlist

print("myflatten list=", myflatten([1,[5,6,7],3,4,[7,8,9]]))
NendoTaka
  • 1,224
  • 8
  • 14
  • But with this I find subsequent calls keep adding to outlist created by previous call to the function. How to correct that? – rnso Nov 30 '17 at 17:33
  • @rnso can you give me an example oh what you mean? – NendoTaka Nov 30 '17 at 17:35
  • Try `print(myflatten([1])); print(myflatten([2]))` on your function. You will get `[1,2]` as output of second command. – rnso Nov 30 '17 at 17:40
  • Interesting, learned something new. Kevin's answer works better since it doesn't use the outlist as a parameter. I could update this one but since his answer works, I won't unless you would like me to. – NendoTaka Nov 30 '17 at 17:47
  • See this: https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument – rnso Nov 30 '17 at 17:48
  • Yep, that's what I had seen in Kevin's link, which means that using outlist as a parameter is a bad idea. There are some other answers that work better for that reason. – NendoTaka Nov 30 '17 at 17:52
1

You've created an infinite list. The [...] entries in the list point back to the list itself. See this answer for more details.

This is because when you make a recursive call, you pass in the outlist object itself, then return it and append it to itself. A subtle problem! But an easy fix; you'll want to use = for the recursive call, not append. Or perhaps extend, and pass in an empty list.

def myflatten(slist):
    outlist = []
    for sl in slist:
        if type(sl) == list:    
            outlist.extend(myflatten(sl))
        else: 
            outlist.append(sl)
    return outlist

You can even get rid of a parameter, which is nice.

colopop
  • 441
  • 3
  • 13
1

Another option that doesn't use list.extend. I'd rearrange your code a bit, and try to avoid default parameters:

def myflatten(slist):
    flat = []
    if isinstance(slist, list):
        for item in slist:
            flat += myflatten(item)
    else:
        flat.append(slist)
    return flat
Mr. Xcoder
  • 4,719
  • 5
  • 26
  • 44