[Views and opinions are my own.]
First and foremost, I love Python. I believe Python is one of the best choices the mainstream development community provides for doing Functional Programming. It provides all of the bells and whistles necessary to do solid, well-thought (dare I say lawful?) FP.
One could say the hallmark features of FP are
functional values
free monoid with a fold
lambdas
strong types
Python does a wonderful job of providing all of these to a Developer. From these building blocks, we can mostly get to Type Classes in Python.
“But Hey! Wait just a moment! I thought you hated Python!!!” I do. Well… not properly, but I hate how Python is typically used. It appears, someone out there is teaching a large subset of the Python community to write Python like it is a worse version of Java (Yes, things can get worse than Java, so count your blessings!). Just a few points.
Some data can be stored not in a class
Some classes can be alone in the world with no Parent or Child classes defined
No one ever said Functions/Methods must be coupled to data
All too often I find myself in a sea of poorly conceived class hierarchies wherein “inheritance” is misappropriated to restrict rather than to extend capabilities and behaviors. This is the type of Python I hope to avoid in the future but know I will be faced with in short order.
Python is Good for FP
Yes. It is.
Python has Functions as Values
def add(a,b): return a + b compose = add print(f"compose is add: {compose(1, 2) == add(1, 2)}") def same(f, g, a, b): print(f"{f(a, b) == g(a, b)} for and ") same(add, compose, 1, 2)
This displays
compose is add: True True for 1 and 2
Python has a Free Monoid with a Fold
from functools import reduce free = [1,2,3,4,5,6] def c1(a, b): return a + b def c2(a, b): return a * b def c3(a, b): return str(a) + str(b) print(reduce(c1, free, 0)) print(reduce(c2, free, 1)) print(reduce(c3, free, ""))
This displays
21 720 1234
Python has Lambdas
from functools import reduce free = [1,2,3,4,5,6] print(reduce(lambda a,b: a + b, free)) print(reduce(lambda a,b: a * b, free)) print(reduce(lambda a,b: str(a) + str(b), free))
This displays
21 720 123456
Python has Strong Types
Strong types are important for FP. Static types are not.
Strong types ensure the data one function writes is the data another function reads. It ensures the type of a value is static through the lifetime of that value.
Static types ensure the type of a name is static through the lifetime of that name. Static vs Dynamic typing is only important in applications where there is use of the assignment operator outside of declaration. As functional programmers, we do not do this, even if it is allowed. A “limitation” or “inconvenience” caused by dynamic typing can simply be overcome by discipline.
a = '1' b = 1 print(f"a= is a ; b= is a ; a == b is {a == b}") print(f"a+a gives ") print(f"b+b gives ") print(f"a+b error") print(a+b)
This displays
a=1 is a <class 'str'>; b=1 is a <class 'int'>; a == b is False a+a gives 11 b+b gives 2 a+b error Traceback (most recent call last): File "C:\Users\dread\OneDrive\DreadedSoftware\Talks\y2022\hatepython\04.py", line 12, in <module> print(a+b) TypeError: can only concatenate str (not "int") to str
In Python, Everything is Mutable
This, like Dynamic Typing, is not a problem for a disciplined functional programmer.
a = [1,2,3,4,5,6,7] print(a) for i in range(len(a)): if 0 == i % 2: a[i] = -a[i] print(a)
This displays
[1, 2, 3, 4, 5, 6, 7] [-1, 2, -3, 4, -5, 6, -7]
If we avoid the = operator, things should work out great.
Applying the Basics
Say we have two computations which apply an operation across a list of numbers to produce a new number.
from functools import reduce a = [1,2,3,4] def black_box_extreme_computation_1(sequence): return reduce(lambda a,b: a+b, sequence) def black_box_extreme_computation_2(sequence): return reduce(lambda a,b: a*b, sequence) print(f"add: ") print(f"multiply: ")
This displays
add: 10 multiply: 24
The problem is the functions differ only by the operation applied. this is very WET code, and we like DRY. Luckily, we can pass functions as values in Python.
a = [1,2,3,4] def add(a,b): return a + b def multiply(a,b): return a*b def black_box_extreme_computation(sequence): def inner(f): return reduce(f, sequence) return inner print(f"add: ") print(f"multiply: ")
This displays
add: 10 multiply: 24
We have gotten rid of the repetition, but that is not good
enough. Why? Code is meant to be read. A function which takes
a simple functional value f is not good enough. We want to
provide enough information to the reader so that the reader does
not need to read the entire function to understand how and why
the f parameter is used.
Further, gone are the days of "I write code so that a competent engineer can understand it." There are a lot of boot camp developers out there. These boot camps are like 3 months long. these people have literally been coding for 3 months. Even if someone with 3 months of experience reads most functions they will likely misunderstand something, misinterpret something or miss something important. We need to do some work up front to ensure a "competent engineer" (whatever that means) can understand the function just by reading the prototype AND a fresh-out-of-camp colleague will either understand the function just by the prototype or immediately ask someone "What do I do here?"
More succinctly, we need to ensure we put enough information into the function prototype so that someone who does not "just know" what things mean, will know to ask a question.
For example, let's require our f to be Associative. That
information is not easily ascertainable, and someone, at some
point in time will try to shove something non associative
into the mix. Like maybe:
def alternate(): def switcher(): n = True while True: n = not n yield n gen = switcher() def inner(a, b): if next(gen): return add(a,b) else: return multiply(a,b) return inner
Any application which requires associativity will produce odd stuff in this case, and we want to avoid these types of bugs because, they are incredibly difficult to find and fix in a language with no compiler.
To solve this, we will use a class and type annotations. Even though types are not enforced in Python, annotations make it easy to tell future developers (including yourself 3 weeks from now) what it is your intention was in writing the code.
from abc import ABC, abstractmethod class AssociativeOperator(ABC): @abstractmethod def combine(self, a, b): pass from functools import reduce a = [1,2,3,4] class Add(AssociativeOperator): def combine(self, a,b): return a+b class Multiply(AssociativeOperator): def combine(self, a,b): return a*b def black_box_extreme_computation(sequence): def inner(f: AssociativeOperator): return reduce(f.combine, sequence) return inner
Now, it is super clear that we want an associative operation. For good measure, let’s do something similar with a Monoid.
from abc import ABC, abstractmethod class Monoid(ABC): a = None @abstractmethod def combine(self, a, b): pass from functools import reduce a = [1,2,3,4] class Add(Monoid): a = 0 def combine(self, a,b): return a+b class Multiply(Monoid): a = 1 def combine(self, a,b): return a*b def black_box_extreme_computation(sequence): def inner(f: Monoid): return reduce(f.combine, sequence, f.a) return inner
A simple change, and we went from requiring just a closed Associative Operator (Semigroup), to requiring both a closed Associative Operator and an identity item.
These very much are type classes; however, this encoding still
leaves something to be desired. In programming languages that
support "real functional programming", a function that looks like
f(input)(typeclass_instance) can nearly automatically
discover which typeclass_instance to choose.
For instance in Scala arguments can be automagically inferred
by using the implicit keyword. In Haskell, typeclasses are
well-supported at the compiler level and just declaring
a type class instance in a function prototype delivers the
instance.
What is needed is a semi-automatic way to pass in a function which is enhanced in some way by another function.
Enter the Decorator
def noDecorator(): def log(f, message): print(f(message)) def formatter(message): import datetime delim = { 'begin': '~** ', 'end' : ' **~' } return f"[] " log(formatter, "first") log(formatter, "second") log(formatter, "third") noDecorator() def withDecorator(): def logger(f): def inner(*args): print(f(*args)) return inner @logger def log(message): import datetime delim = { 'begin': '~** ', 'end' : ' **~' } return f"[] " log("first") log("second") log("third") withDecorator()
This displays
[2022-07-17 02:38:08.810432] ~** first **~ [2022-07-17 02:38:08.811466] ~** second **~ [2022-07-17 02:38:08.811466] ~** third **~ [2022-07-17 02:38:08.811466] ~** first **~ [2022-07-17 02:38:08.812467] ~** second **~ [2022-07-17 02:38:08.812467] ~** third **~
Since we are discussing Typeclasses, it is important to note we can stack decorators to apply multiple enhancements to the same function.
def truncate(f): def inner(message): return f(message[:3]) return inner def logger(f): def inner(message): print(f(message)) return inner @logger @truncate def log(message): import datetime delim = { 'begin': '~** ', 'end' : ' **~' } return f"[] " print(log("first"))
This displays
[2022-07-17 02:41:15.011042] ~** fir **~
Let’s enhance our same typeclass example with Monoid with Decorators to almost automatically pass in our instances
Semi-Automatic Choice
from functools import reduce from abc import ABC, abstractmethod import random a = [1,2,3,4] class Monoid(ABC): def combine(a, b): pass class Add(Monoid): def combine(a,b): return a+b class Multiply(Monoid): def combine(a,b): return a*b def monoid(F: Monoid): def decorator(f): def inner(*args, **kwargs): return f(*args, **kwargs)(F) return inner return decorator def black_box_extreme_computation(sequence): def inner(f: Monoid): return reduce(f.combine, sequence) return inner @monoid(Multiply) def pi(sequence): return black_box_extreme_computation(sequence) @monoid(Add) def sigma(sequence): return black_box_extreme_computation(sequence) print(f"pi(a) =\n ") print(f"pi(random.sample(a, len(a))) =\n {pi(random.sample(a, len(a)))}") print(f"pi([*a, 5]) =\n {pi([*a, 5])}") print(f"sigma(a) =\n ") print(f"sigma(random.sample(a, len(a))) =\n {sigma(random.sample(a, len(a)))}") print(f"sigma([*a, 5]) =\n {sigma([*a, 5])}")
This displays
pi(a) = 24 pi(random.sample(a, len(a))) = 24 pi([*a, 5]) = 120 sigma(a) = 10 sigma(random.sample(a, len(a))) = 10 sigma([*a, 5]) = 15
To get rid of the need to explicitly pass in the typeclass instance in argument, we created a function which takes a typeclass instance as an argument and returns a decorator. Decorators are simply functions, functions are values, why not return a decorator as the result of a function? Our decorator is indeed a currying operator.
This gets us to semi-automatic typeclass use. There is a fair bit of pageantry and ceremony in defining typeclasses, there is no auto derivation, there is no compiler help; however, at least we have marked functions as requiring well-known typeclasses, and we can write Python code that looks at least a little bit like it was written in a language which enforces the types of discipline we take for granted in other environments.
Monads
Setup
from functools import reduce from abc import ABC a = [1,2,3,4]
A Functor is just a function mapping an item in our source category (types) into an item in our target category (types inside of some other type). We will make one for List and for “Optional”. Note: in Python everything is Optional so this is a fancy version of the identity, but it still makes for a nice example.
class Functor(ABC): def lift(a): pass def map(f): pass class ListFunctor(Functor): def lift(a): return [a] def map(f): def inner(a): return map(f, a) return inner class AnyFunctor(Functor): def lift(a): return a def map(f): def inner(a): if a != None: return f(a) else: return a return inner
A Functor and some special Natural Transformations make up a Monad. So let’s do it for List and Optional.
class Monad(ABC): F: Functor = None def bind(a, f): pass class ListMonad(Monad): F = ListFunctor def bind(self, a, f): listList = self.F.map(f)(a) return [b for a in listList for b in a] class AnyMonad(Monad): F = AnyFunctor def bind(self, a, f): optOpt = self.F.map(f)(a) return optOpt def monad(F: Monad): def decorator(f): def inner(*args, **kwargs): return f(*args, **kwargs)(F) return inner return decorator
Just for completeness, we need an operation to chain monadic
computations easily. Every “real functional language” provides
such a mechanism (Haskell: >>=; Scala: for), so
let’s do it here too.
def chain(a, *args): def inner(F: Monad): return reduce(lambda a,b: F.bind(F, a, b), args, a) return inner @monad(ListMonad) def flatMap(a, *args): return chain(a, *args) @monad(AnyMonad) def noneCheck(a, *args): return chain(a, *args)
Some functions to chain together
def toRange(a): return list(range(a)) def repeater(a): return [a] * 2 def doubler(a): return [a*2] def stringToInt(a): try: return int(a) except: None def intToList(a): return list(range(a))
And we have…
print(f"flatMap(a, doubler, repeater, toRange) =\n {flatMap(a, doubler, repeater, toRange)}") print(f"noneCheck('a', stringToInt, intToList) =\n {noneCheck('a', stringToInt, intToList)}") print(f"noneCheck('7', stringToInt, intToList) =\n {noneCheck('7', stringToInt, intToList)}") print(f"flatMap(noneCheck('7', stringToInt, intToList), intToList) =\n {flatMap(noneCheck('7', stringToInt, intToList), intToList)}")
Which displays
flatMap(a, doubler, repeater, toRange) = [0, 1, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7] noneCheck('a', stringToInt, intToList) = None noneCheck('7', stringToInt, intToList) = [0, 1, 2, 3, 4, 5, 6] flatMap(noneCheck('7', stringToInt, intToList), intToList) = [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5]
Conclusion
We have typeclass-based, Monadic operations in Python which is a Dynamically typed language. This requires strong typing and functions as values.
We use classes to model Typeclasses.
We use the facts that functions are values and decorators are functions to give us a currying function which we then use to give us semi-automatic typeclass instance choice.
We have proven this sound for Semigroups, Monoids, Functors and Monads. There is no reason to believe it would fail for Groupoids, Groups, Applicatives or any other Typeclasses that are representable in Python.