Yet Another Python Multimethod Decorator, Part 5: Duckfaces

OK, so our multimethod decorator is progressing nicely. It’s robust and versatile in ways it wasn’t before, handling a whole bunch of common situations sensibly in a way our starting point didn’t. Let’s do something with it that might actually seem reasonable to want to do.

flatten is a simple function which takes a list, and returns a new list which contains all the items in the list, unless any of those items were themselves a list, in which case their contents are inserted into the list instead. For example, flatten([1, 2, [3, 4], 5, [6, [7, 8], 9, [0]]]) returns [1, 2, 3, 4, 5, 6, 7, 8, 9, 0].

So, we end up with something like:

@multimethod(list)
def flatten(xs):
  flattened = []
  for x in xs:
    flattened.extend(flatten(x))   
  return flattened
   
@multimethod(???):
def flatten(x): return [x]

Wait a minute – what should ??? be?. We don’t have a way of saying “anything else” here. We could say @multimethod(object), which would then match everything, but at that point we have a situation that both implementations can accept a list, as a list is both a list (obviously!) and an object. So, now we need to decide which implementation to pass it to. There are some superficially straightforward solutions to this, but as I’ll hopefully eventually get to, that leads down a very nasty rabbit hole.

What we really want is a direct concept of “anything else” – if no other implementations match, use this one. So, let’s introduce a @default decorator, and if we’re approaching it like that, let’s rename the multimethod decorator to @case, so now our multimethod looks like so:

@case(list)
def flatten(xs): 
   flattened = []
   for x in xs:
      flattened.extend(flatten(x))
   return flattened

@default
def flatten(x): return [x]

OK, nice, that’s a lot better, or I think so at least. Now we can get to the point. This function will flatten a list for us. What if we want to flatten a tuple?

b = (1, 2, (3), 4, (5, ((6, 7), 8), 9), 0)
>>> flatten(b)
[(1, 2, 3, 4, (5, ((6, 7), 8), 9), 0)]

Well, obviously, it doesn’t handle tuples: it was coded for lists. Can we make it work for tuples and lists? After all, they’re both sequence types – all we need is for them to be iterable. There isn’t however, a common iterable class that both extend.

For that matter, nor should there be. Python “uses” duck typing, in that if the method you’re trying to call exists, then it won’t throw a type error. To be Pythonic, we shouldn’t be looking at the class hierarchy to determine whether something’s iterable or not. We should be looking at its duck-typed-interface, or duckface for short.

How do we define if something’s iterable: if it implements __iter__(), it’s iterable. Similarly, for our original circle/rectangle case, it’s a circle if it’s got a centre and a radius, and it’s a rectangle if it has a left, a right, a top and a bottom. Python doesn’t have a concept of interfaces, so I think we’ll have to introduce our own:

class Duckface:
   def __init__(self, *required_attribs):
      self.required_attribs = required_attribs

   def satisfied_by(self, x):
      return all((hasattr(x, attrib) for attrib in self.required_attribs))

This isn’t as sophisticated as it could be: it doesn’t check argument lists, return types, or even whether something’s a method or a field. It can’t distinguish a duck (which can quack) from a homeopathy clinic (which has a quack). But then, there’s no way to look at return types in Python, nor argument types – this is probably as far as you want to go down that particular route. Anything more sophisticated than this is both way more of a pain to describe and has some gnarly corner-case consequences.

Note that any object satisfies many duckfaces, and has no idea that duckfaces even exist (unlike, for example, Java’s interfaces, which have to be explicitly implemented). We’re just describing and modelling an emergent property of Python’s dynamic type system, after all.

This now poses an interesting question. Duckfaces are more convenient when we want to describe iterables, for example, but it’s easier and clearer to distinguish Circle and Rectangle with class names. We don’t want to throw the baby out with the bathwater on this one: we really want our multimethods to handle both classes (and if we’re doing that, we have to respect subclassing) and duckfaces, and we don’t want to have to think about which one we’re using: they’re both types to us.

Easily done. We just have to make our checking of the cases a little more complicated: reflectively determine if our requirement is a class or a duckface. If the requirement is a class, use isinstance, else use satisfied_by. Then we can handle any nested sequences, be they lists, tuples, ranges, or a mix-and-match, like this:

iterable = Duckface("__iter__")

@case(iterable)
def flatten(xs): 
   flattened = []
   for x in xs:
      flattened.extend(flatten(x))
   return flattened

@default
def flatten(x): return [x]

flatten([1, 2, (3, 4), 5, ([range(6..9)], 9), 0])

Which, of course, returns [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], just like we wanted.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s