Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How can I write a function fmap that returns the same type of iterable that was inputted?

How can I write a function "fmap", with this properties :

>>> l = [1, 2]; fmap(lambda x: 2*x, l)
[2, 4]
>>> l = (1, 2); fmap(lambda x: 2*x, l)
(2, 4)
>>> l = {1, 2}; fmap(lambda x: 2*x, l)
{2, 4}

(I search a kind of "fmap" in haskell, but in python3).

I have a very ugly solution, but there is certainly a solution more pythonic and generic ? :

def fmap(f, container):
    t = container.__class__.__name__
    g = map(f, container)
    return eval(f"{t}(g)")
like image 932
HNoob Avatar asked Jan 02 '19 10:01

HNoob


3 Answers

Instantiate directly rather than via eval

__class__ can also be used to instantiate new instances:

def mymap(f, contener):
    t = contener.__class__
    return t(map(f, contener))

This removes the need for eval, use of which is considered poor practice. As per @EliKorvigo's comment, you may prefer built-in type to a magic method:

def mymap(f, contener):
    t = type(contener)
    return t(map(f, contener))

As explained here and in the docs:

The return value is a type object and generally the same object as returned by object.__class__.

"Generally the same" should be considered "equivalent" in the case of new-style classes.

Testing for an iterable

You can check/test for an iterable in a couple of ways. Either use try / except to catch TypeError:

def mymap(f, contener):
    try:
        mapper = map(f, contener)
    except TypeError:
        return 'Input object is not iterable'
    return type(contener)(mapper)

Or use collections.Iterable:

from collections import Iterable

def mymap(f, contener):
    if isinstance(contener, Iterable):
        return type(contener)(map(f, contener))
    return 'Input object is not iterable'

This works specifically because built-in classes commonly used as containers such as list, set, tuple, collections.deque, etc, can be used to instantiate instances via a lazy iterable. Exceptions exist: for example, str(map(str.upper, 'hello')) will not work as you might expect even though str instances are iterable.

like image 102
jpp Avatar answered Nov 14 '22 23:11

jpp


Using the type of the input as a converter is not necessarily working in all occasions. map is just using the "iterability" of its input to produce its output. In Python3 this is why map returns a generator instead of a list (which is just more fitting).

So a cleaner and more robust version would be one which explicitly expects the various possible inputs it can handle and which raises an error in all other cases:

def class_retaining_map(fun, iterable):
  if type(iterable) is list:  # not using isinstance(), see below for reasoning
    return [ fun(x) for x in iterable ]
  elif type(iterable) is set:
    return { fun(x) for x in iterable }
  elif type(iterable) is dict:
    return { k: fun(v) for k, v in iterable.items() }
  # ^^^ use .iteritems() in python2!
  # and depending on your usecase this might be more fitting:
  # return { fun(k): v for k, v in iterable.items() }
  else:
    raise TypeError("type %r not supported" % type(iterable))

You could add a case for all other iterable values in the else clause of cause:

  else:
    return (fun(x) for x in iterable)

But that would e. g. return an iterable for a subclass of set which might not be what you want.

Mind that I'm deliberately not using isinstance because that would make a list out of a subclass of list, for instance. I figure that this is explicitly not wanted in this case.

One could argue that anything which is a list (i. e. is a subclass of list) needs to comply to have a constructor which returns a thing of this type for an iteration of elements. And likewise for subclasses of set, dict (which must work for an iteration of pairs), etc. Then the code might look like this:

def class_retaining_map(fun, iterable):
  if isinstance(iterable, (list, set)):
    return type(iterable)(fun(x) for x in iterable)
  elif isinstance(iterable, dict):
    return type(iterable)((k, fun(v)) for k, v in iterable.items())
  # ^^^ use .iteritems() in python2!
  # and depending on your usecase this might be more fitting:
  # return type(iterable)((fun(k), v) for k, v in iterable.items())
  else:
    raise TypeError("type %r not supported" % type(iterable))
like image 33
Alfe Avatar answered Nov 14 '22 23:11

Alfe


I search a kind of "fmap" in haskell, but in python3

First, let's discuss Haskell's fmap to understand, why it behaves the way it does, though I assume you are fairly familiar with Haskell considering the question. fmap is a generic method defined in the Functor type-class:

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    ...

Functors obey several important mathematical laws and have several methods derived from fmap, though the latter is sufficient for a minimal complete functor instance. In other words, in Haskell types belonging to the Functor type-class implement their own fmap functions (moreover, Haskell types can have multiple Functor implementations via newtype definitions). In Python we don't have type-classes, though we do have classes that, while less convenient in this case, allow us to simulate this behaviour. Unfortunately, with classes we can't add functionality to an already defined class without subclassing, which limits our ability to implement a generic fmap for all builtin types, though we can overcome it by explicitly checking for acceptable iterable types in our fmap implementation. It's also literally impossible to express higher-kinded types using Python's type system, but I digress.

To summarise, we've got several options:

  1. Support all Iterable types (@jpp's solution). It relies on constructors to convert an iterator returned by Python's map back into the original type. That is the duty of applying a function over the values inside a container is taken away from the container. This approach differs drastically from the functor interface: functors are supposed to handle the mapping themselves and handle additional metadata crucial to reconstruct the container.
  2. Support a subset of readily mappable builtin iterable types (i.e. builtins that don't carry any important metadata). This solution is implemented by @Alfe, and, while less generic, it is safer.
  3. Take solution #2 and add support for proper user-defined functors.

This is my take on the third solution

import abc
from typing import Generic, TypeVar, Callable, Union, \
    Dict, List, Tuple, Set, Text

A = TypeVar('A')
B = TypeVar('B')


class Functor(Generic[A], metaclass=abc.ABCMeta):

    @abc.abstractmethod
    def fmap(self, f: Callable[[A], B]) -> 'Functor[B]':
        raise NotImplemented


FMappable = Union[Functor, List, Tuple, Set, Dict, Text]


def fmap(f: Callable[[A], B], fmappable: FMappable) -> FMappable:
    if isinstance(fmappable, Functor):
        return fmappable.fmap(f)
    if isinstance(fmappable, (List, Tuple, Set, Text)):
        return type(fmappable)(map(f, fmappable))
    if isinstance(fmappable, Dict):
        return type(fmappable)(
            (key, f(value)) for key, value in fmappable.items()
        )
    raise TypeError('argument fmappable is not an instance of FMappable')

Here is a demo

In [20]: import pandas as pd                                                                        

In [21]: class FSeries(pd.Series, Functor): 
    ...:      
    ...:     def fmap(self, f): 
    ...:         return self.apply(f).astype(self.dtype)
    ...:                                                                                            

In [22]: fmap(lambda x: x * 2, [1, 2, 3])                                                           
Out[22]: [2, 4, 6]

In [23]: fmap(lambda x: x * 2, {'one': 1, 'two': 2, 'three': 3})                                    
Out[23]: {'one': 2, 'two': 4, 'three': 6}

In [24]: fmap(lambda x: x * 2, FSeries([1, 2, 3], index=['one', 'two', 'three']))   
Out[24]: 
one      2
two      4
three    6
dtype: int64

In [25]: fmap(lambda x: x * 2, pd.Series([1, 2, 3], index=['one', 'two', 'three']))                 
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-27-1c4524f8e4b1> in <module>
----> 1 fmap(lambda x: x * 2, pd.Series([1, 2, 3], index=['one', 'two', 'three']))

<ipython-input-7-53b2d5fda1bf> in fmap(f, fmappable)
     34     if isinstance(fmappable, Functor):
     35         return fmappable.fmap(f)
---> 36     raise TypeError('argument fmappable is not an instance of FMappable')
     37 
     38 

TypeError: argument fmappable is not an instance of FMappable

This solution allows us to define multiple functors for the same type via subclassing:

In [26]: class FDict(dict, Functor):
   ...:     
   ...:     def fmap(self, f):
   ...:         return {f(key): value for key, value in self.items()}
   ...: 
   ...: 

In [27]: fmap(lambda x: x * 2, FDict({'one': 1, 'two': 2, 'three': 3}))     
Out[27]: {'oneone': 1, 'twotwo': 2, 'threethree': 3}
like image 20
Eli Korvigo Avatar answered Nov 14 '22 22:11

Eli Korvigo