"Pythonic" class level recursion?

Question

I am creating a class that inherits from collections.UserList that has some functionality very similar to NumPy's ndarray (just for exercise purposes). I've run into a bit of a roadblock regarding recursive functions involving the modification of class attributes:

Let's take the flatten method, for example:

class Array(UserList):
    def __init__(self, initlist):
        self.data = initlist

    def flatten(self):
        # recursive function
        ...

Above, you can see that there is a singular parameter in the flatten method, being the required self parameter. Ideally, a recursive function should take a parameter which is passed recursively through the function. So, for example, it might take a lst parameter, making the signature:

Array.flatten(self, lst)

This solves the problem of having to set lst to self.data, which consequently will not work recursively, because self.data won't be changed. However, having that parameter in the function is going to be ugly in use and hinder the user experience of an end user who may be using the function.

So, this is the solution I've come up with:

def flatten(self):
    self.data = self.__flatten(self.data)

def __flatten(self, lst):
    ...
    return result

Another solution could be to nest __flatten in flatten, like so:

def flatten(self):
    def __flatten(lst):
        ...
        return result
    self.data = __flatten(self.data)

However, I'm not sure if nesting would be the most readable as flatten is not the only recursive function in my class, so it could get messy pretty quickly.

Does anyone have any other suggestions? I'd love to know your thoughts, thank you!

Answer 1

A recursive method need not take any extra parameters that are logically unnecessary for the method to work from the caller's perspective; the self parameter is enough for recursion on a "child" element to work, because when you call the method on the child, the child is bound to self in the recursive call. Here is an example:

from itertools import chain

class MyArray:
    def __init__(self, data):
        self.data = [
            MyArray(x) if isinstance(x, list) else x
            for x in data]
    def flatten(self):
        return chain.from_iterable(
            x.flatten() if isinstance(x, MyArray) else (x,)
            for x in self.data)

Usage:

>>> a = MyArray([[[1, 2], [3, 4]], [[5, 6], [7, 8]]])
>>> list(a.flatten())
[1, 2, 3, 4, 5, 6, 7, 8]

Answer 2

Since UserList is an iterable, you can use a helper function to flatten nested iterables, which can deal likewise with lists and Array objects:

from collections import UserList
from collections.abc import Iterable


def flatten_iterable(iterable):
    for item in iterable:
        if isinstance(item, Iterable):
            yield from flatten_iterable(item)
        else:
            yield item


class Array(UserList):
    def __init__(self, initlist):
        self.data = initlist

    def flatten(self):
        self.data = list(flatten_iterable(self.data))


a = Array([[1, 2], [3, 4]])
a.flatten(); print(a)  # prints [1, 2, 3, 4]

b = Array([Array([1, 2]), Array([3, 4])])
b.flatten(); print(b)  # prints [1, 2, 3, 4]

Answer 3

barrier of abstraction

Write array as a separate module. flatten can be generic like the example implementation here. This differs from a_guest's answer in that only lists are flattened, not all iterables. This is a choice you get to make as the module author -

# array.py

from collections import UserList

def flatten(t):                     # generic function
  if isinstance(t, list):
    for v in t:
      yield from flatten(v)
  else:
    yield t

class array(UserList):
  def flatten(self):
    return list(flatten(self.data)) # specialization of generic function

why modules are important

Don't forget you are the module user too! You get to reap the benefits from both sides of the abstraction barrier created by the module -

1. As the author, you can easily expand, modify, and test your module without worrying about breaking other parts of your program
2. As the user, you can rely on the module's features without having to think about how the module is written or what the underlying data structures might be

# main.py

from array import array

t = array([1,[2,3],4,[5,[6,[7]]]])  # <- what is "array"?

print(t.flatten())

[1, 2, 3, 4, 5, 6, 7]

As the user, we don't have to answer "what is array?" anymore than you have to answer "what is dict?" or "what is iter?" We use these features without having to understand their implementation details. Their internals may change over time, but if the interface stays the same, our programs will continue to work without requiring change.

reusability

Good programs are reusable in many ways. See python's built-in functions for proof of this, or see the the guiding principles of the Unix philosophy -

1. Write programs that do one thing and do it well.
2. Write programs to work together.

If you wanted to use flatten in other areas of our program, we can reuse it easily -

# otherscript.py

from array import flatten

result = flatten(something)

Answer 4

Typically, all methods of a class have at least one argument which is called self in order to be able to reference the actual object this method is called on.

If you don't need self in your function, but you still want to include it in a class, you can use @staticmethod and just include a normal function like this:

class Array(UserList):
    def __init__(self, initlist):
        self.data = initlist

    @staticmethod
    def flatten():
        # recursive function
        ...

Basically, @staticmethod allows you to make any function a method that can be called on a class or an instance of a class (object). So you can do this:

arr = Array()
arr.flatten()

as well as this:

Array.flatten()

Here is some further reference from Pyhon docs: https://docs.python.org/3/library/functions.html#staticmethod