Pythonic Encoding Through Functional Style: Iterable Monad

Python is a powerful language that is ideal for scripting and rapid application development. Python supports functional-style programming, as functions are treated as first-order values. It allows writing more concise and expressive Python code, or more "Pythonic code." In this article, we introduce Iterable Monad in Python. Through the implementation of making Iterable Python collections monadic, we demonstrate the power of functional features in Python and the elegance that monad can bring to Python encoding. We also prove that the Iterable Monad satisfies the Monad law. Given that iterables are heavily used and monadic encoding is not supported in native Python, this mechanism can obtain significant improvement in Python programming.

Monad

In functional programming, a monad is a structure that combines program fragments (functions) and wraps their return values in a type with additional computation. In addition to defining a wrapping monadic type, monads define two operators: one to wrap a value in the monad type and another to compose together functions that output values of the monad type (these are known as monadic functions).

General-purpose languages use monads to reduce boilerplate code needed for common operations (such as dealing with undefined values or fallible functions or encapsulating bookkeeping code). Functional languages use monads to turn complicated sequences of functions into succinct pipelines that abstract away control flow and side effects.[1]

In Haskell, the above definition can be expressed in two functions as follows:

return :: a -> M a 
bind :: (M a) -> (a -> M b) -> (M b)

The first function is a wrapper function that takes a value and wraps it up in a monad;

The second is a function that applies the function to the value and wraps the result in a monad.

In this article, we follow the Python naming convention and use __init__() as the name of the wrapper function and flat_map() as the name of the bind function

A Monad satisfies the following laws:

Left Identity

Applying a function f using the flat_map function to a value x lifted by the identity function is equivalent to applying the function f directly to the value x:

Right Identity

The flat_map function using the identity function as the function f results in the original monadic value:

x.flat_map(y => __init__(y)) = x

Associativity

Applying two functions f and g to a monad value using a sequence of flat_map calls is equivalent to applying g to the result of the application of the flat_map function using f as the parameter:

x.flat_map(f).flat_map(g) = x.flat_map(x => f(x).flat_map(g))

A generic interface is defined as:

class Monad:
    def __init__(self, value: object = None):
	pass        
    def flat_map(self, f:  Callable) -> Monad:
        pass

Iterable Monad for Python

Monads have been introduced into Python programming to solve various problems, for instance, Maybe Monad, Either Monad, Promise Monad, IO Monad, etc[2]. In this article, we propose to lift the Python Iterables to a monad such that the operations over the Iterables can enjoy the same benefit a Monad can offer.

A Python Iterable is a collection of items that can be traversed through. The item in the collection is accessed through an iterator using function __iter__() and __next__(). More specifically, items in the iterable can be accessed as follows:

for item in an_iterable:
	Print (x)

The Python-native map function takes a function and maps it to the Iterable, resulting in another iterable. However, when an iterable is boxed into a monad, by lifting an iterable into a monad, things become more interesting. We will discuss its unique characteristics later.

Python Iterable monad is to wrap the Python iterables into a monad, with the ability to apply the mapping function to each element of the given Iterable. The difference between a monadic flat_map and a Python native mapping function is a monadic flat_map() is aware of monadic context and takes the iterable as a whole.

There are four iterable collections in Python: list, tuple, set, and dictionary.

A common interface can be encoded as follows:

class IterableMonad:
	def flat_map(self, f:  Callable) -> 'IterableMonad':
		return self.map(f).flatten()

flat_map() acts as a bind function that takes a Python iterable, wraps the mapped result to a monad and unpacks to return a new monad. Each iterable monad has to provide a map() and a flatten() implementation according to their own characteristics, for instance, ListMonad:

class ListMonad(IterableMonad):
	def map(self, f:Callable):
		return ListMonad((list)(map(f, self.value)))
	def flatten(self):
		return ListMonad(list([item for monad in self.value for item in monad.value]))

*In addition, we implement __eq__() to check the equality of two monads for test purposes:

def __eq__(self, other):
	return self.value == other.value if isinstance(other, type(self)) else False

**SetMonad: the implementation is slightly different from other Python iterables as set elements are required to be hashable.

Monad Law Compliance

We prove that our Iterable monads satisfy Monad Law. For instance, a ListMonad:

#left identity
 a = 2
 lhs = ListMonad([a]).flat_map(f)
 rhs = f(a)
 print(lhs == rhs)

 # right identity
 lhs=ListMonad([a]).flat_map(lambda x: ListMonad([x]))
 rhs=ListMonad([a])
 print(lhs == rhs)

 # associativity
 m = ListMonad([1, 2])
 lhs = m.flat_map(f).flat_map(g)
 rhs = m.flat_map(lambda x: f(x).flat_map(g))
 print(lhs == rhs)

A DictMonad:

#left identity
 d = {'a': 1, 'b':2}
 lhs = DictMonad(d).flat_map(f)
 rhs = f(d)
 print(lhs == rhs)
 
 # right identity
 lhs=DictMonad(d).flat_map(lambda x: DictMonad(x))
 rhs=DictMonad(d)
 print(lhs == rhs)
 
 # associativity
 m = DictMonad(d)
 lhs = m.flat_map(f).flat_map(g)
 rhs = m.flat_map(lambda x: f(x).flat_map(g))
 print(lhs == rhs)

Summary

In this article, we introduced the idea of lifting Python Iterables to monads that allows us to write Pythonic code with safety, readability, and modularity, thus allowing us to write Python code with monadic instead of idiomatic style. We also provided a reference implementation and proved that the implementation abides by Monad laws. 

The reference implementation can be found here.

References:

[1] https://en.wikipedia.org/wiki/Monad_(functional_programming)

[2] https://dev.to/hamzzak/mastering-monad-design-patterns-simplify-your-python-code-and-boost-efficiency-kal