Do something to a collection and then return the same type as the collection

user_430766 0
Viewed 287

I want to apply a function f to a collection xs but keep its type. If I use map, I get a 'map object':

def apply1(xs, f):
  return map(f, xs)

If I know that xs is something like a list or tuple I can force it to have the same type:

def apply2(xs, f):
  return type(xs)(map(f, xs))

However, that quickly breaks down for namedtuple (which I am currently in a habbit of using) -- because to my knowledge namedtuple needs to be constructed with unpack syntax or by calling its _make function. Also, namedtuple is const, so I cannot iterate over all entries and just change them.

Further problems arise from use of a dict.

Is there a generic way to express such an apply function that works for everything that is iterable?

namedtuple python-3.x type-conversion python
2 Answers

Looks like a perfect task for functools.singledispatch decorator:

from functools import singledispatch


@singledispatch
def apply(xs, f):
    return map(f, xs)


@apply.register(list)
def apply_to_list(xs, f):
    return type(xs)(map(f, xs))


@apply.register(tuple)
def apply_to_tuple(xs, f):
    try:
        # handle `namedtuple` case
        constructor = xs._make
    except AttributeError:
        constructor = type(xs)
    return constructor(map(f, xs))

after that apply function can be simply used like

>>> apply([1, 2], lambda x: x + 1)
[2, 3]
>>> from collections import namedtuple
>>> Point = namedtuple('Point', ['x', 'y'])
>>> p = Point(10, 5)
>>> apply(p, lambda x: x ** 2)
Point(x=100, y=25)

I'm not aware of what is desired behavior for dict objects though, but the greatness of this approach that it is easy to extend.

user_59975960

I have a hunch you're coming from Haskell -- is that right? (I'm guessing because you use f and xs as variable names.) The answer to your question in Haskell would be "yes, it's called fmap, but it only works with types that have a defined Functor instance."

Python, on the other hand, has no general concept of "Functor." So strictly speaking, the answer is no. To get something like this, you'd have to fall back on other abstractions that Python does provide.

ABCs to the rescue

One pretty general approach would be to use abstract base classes. These provide a structured way to specify and check for particular interfaces. A Pythonic version of the Functor typeclass would be an abstract base class that defines a special fmap method, allowing individual classes to specify how they are to be mapped. But no such thing exists. (I think it would be a really cool addition to Python though!)

Now, you can define your own abstract base classes, so you could create a Functor ABC that expects a fmap interface, but you'd still have to write all your own functorized subclasses of list, dict, and so on, so that's not really ideal.

A better approach would be to use the existing interfaces to cobble together a generic definition of mapping that seems reasonable. You'd have to think pretty carefully about what aspects of the existing interfaces you'd need to combine. Just checking to see whether a type defines __iter__ isn't enough, because as you've already seen, a definition of iteration for a type doesn't necessarily translate into a definition of construction. For example, iterating over a dictionary only gives you the keys, but to map a dictionary in this precise way would require iteration over items.

Concrete examples

Here's an abstract base method that includes special cases for namedtuple and three abstract base classes -- Sequence, Mapping, and Set. It will behave as expected for any type that defines any of the above interfaces in the expected way. It then falls back to the generic behavior for iterables. In the latter case, the output won't have the same type as the input, but at least it will work. 

from abc import ABC
from collections.abc import Sequence, Mapping, Set, Iterator

class Mappable(ABC):
    def map(self, f):
        if hasattr(self, '_make'):
            return type(self)._make(f(x) for x in self)
        elif isinstance(self, Sequence) or isinstance(self, Set):
            return type(self)(f(x) for x in self)
        elif isinstance(self, Mapping):
            return type(self)((k, f(v)) for k, v in self.items())
        else:
            return map(f, self)

I've defined this as an ABC because that way you can create new classes that inherit from it. But you can also just call it on an existing instance of any class and it will behave as expected. You could also just use the map method above as a stand-alone function.

>>> from collections import namedtuple
>>> 
>>> def double(x):
...     return x * 2
... 
>>> Point = namedtuple('Point', ['x', 'y'])
>>> p = Point(5, 10)
>>> Mappable.map(p, double)
Point(x=10, y=20)
>>> d = {'a': 5, 'b': 10}
>>> Mappable.map(d, double)
{'a': 10, 'b': 20}

The cool thing about defining an ABC is that you can use it as a "mix-in." Here's a MappablePoint derived from a Point namedtuple:

>>> class MappablePoint(Point, Mappable):
...     pass
... 
>>> p = MappablePoint(5, 10)
>>> p.map(double)
MappablePoint(x=10, y=20)

You could also modify this approach slightly in light of Azat Ibrakov's answer, using the functools.singledispatch decorator. (It was new to me -- he should get all credit for this part of the answer, but I thought I'd write it up for the sake of completeness.)

This would look something like the below. Notice that we still have to special-case namedtuples because they break the tuple constructor interface. That hadn't bothered me before, but now it feels like a really annoying design flaw. Also, I set things up so that the final fmap function uses the expected argument order. (I wanted to use mmap instead of fmap because "Mappable" is a more Pythonic name than "Functor" IMO. But mmap is already a built-in library! Darn.)

import functools

@functools.singledispatch
def _fmap(obj, f):
    raise TypeError('obj is not mappable')

@_fmap.register(Sequence)
def _fmap_sequence(obj, f):
    if isinstance(obj, str):
        return ''.join(map(f, obj))
    if hasattr(obj, '_make'):
        return type(obj)._make(map(f, obj))
    else:
        return type(obj)(map(f, obj))

@_fmap.register(Set)
def _fmap_set(obj, f):
    return type(obj)(map(f, obj))

@_fmap.register(Mapping)
def _fmap_mapping(obj, f):
    return type(obj)((k, f(v)) for k, v in obj.items())

def fmap(f, obj):
    return _fmap(obj, f)

A few tests:

>>> fmap(double, [1, 2, 3])
[2, 4, 6]
>>> fmap(double, {1, 2, 3})
{2, 4, 6}
>>> fmap(double, {'a': 1, 'b': 2, 'c': 3})
{'a': 2, 'b': 4, 'c': 6}
>>> fmap(double, 'double')
'ddoouubbllee'
>>> Point = namedtuple('Point', ['x', 'y', 'z'])
>>> fmap(double, Point(x=1, y=2, z=3))
Point(x=2, y=4, z=6)

A final note on breaking interfaces

Neither of these approaches can guarantee that this will work for all things recognized as Sequences, and so on, because the ABC mechanism doesn't check function signatures. This is a problem not only for constructors, but also for all other methods. And it's unavoidable without type annotations.

In practice, however, it probably doesn't matter much. If you find yourself using a tool that breaks interface conventions in weird ways, consider using a different tool. (I'd actually say that goes for namedtuples too, as much as I like them!) This is the "consenting adults" philosophy behind many Python design decisions, and it has worked pretty well for the last couple of decades.

user_5770880
Related