Expressing GoF Patterns using First-Class Functions
Let’s see if I can express those patterns found in the GoF book, meant for object-oriented languages, in a more functional programming manner.
The essential building block to use in this case is first-class function, a term that wraps entities that can be invoked with parameters, store some state passed into it during their creation (in which case they become closures) and both take functions as parameters and return other functions as results.
Immutability of data operated on will be a nice bonus, but it will be sacrificed in those cases when it is convenient.
The same applies to type checking and the role good types play in design — I will be mostly avoiding questions related to it, given lack of my knowledge on the topic, and lack of desire to prove everything twice.
Singleton
Designing around a singleton is a sign of defeat and a putting a ticking bomb of scalability limits into your application.
In my experience, a singleton in OOP is often needed as a crutch to make objects interact with code already written in a “global manner”. That is, you should start with already pretty hostile design to sense a need for a singleton. And you will soon discover that all the rest of your application starts to orbit around that singleton, serving its needs.
One must jump out of their way to end up with this pattern when writing a new program. If you need one copy of an object, just create one by calling its constructor.
Lack (or at least discouragement) of state mutation, as well as the local nature of name resolution (functions should operate on their arguments and captured state) makes it very contrived to achieve anything matching a Singleton with an FP approach.
An immutable singleton is sort of pointless: one can have as many copies of its state and, short of needing to compare identity of objects (a questionable practice), there will be no way or need to tell those copies apart.
A related Monostate pattern, which hides the global nature of state it manages behind a façade of regular OOP facilities, such as a constructor (always returning the same reference) and a destructor (which does nothing in most cases), is a much better choice. Monostate allows to get rid of that singular state later in a much less disrupting manner to the rest of the application, if you don’t leak implementation of Monostate into its clients. Contrary to that, with a Singleton, its clients always begin with making a global call, i.e., they are always aware about its special nature. It will not be easy to erase this knowledge out of them later.
Abstract Factory
Aside on the nature of object construction
The act of object creation is neither OOP nor FP-pure. It is not object-oriented because, at some point deep inside some factory, you must invoke a non-virtual method: a concrete constructor. It is not purely functional because, after the completed call, you end up with one more name defined where there has just been no name before, and with additional state present in the domain, i.e., with a mutated (global) execution environment. There exists a possible exception of point-free style, but I am not familiar with it enough to comment on it.
It appears to me that this is where the imperative nature of many problems is hard to avoid.
End of aside
An abstract factory function is useful in the FP context the same way it is useful in OOP — it creates an object that implements a known interface while hiding actual details of type choice. The choice is implicitly guided by arguments passed to the factory.
As it is custom for FP code, a guaranteed interface of any constructed object is just a single callable: a pointer to function, closure or a similar thing. It can of course also be a tuple of functions, to imitate a multi-method interface.
As it is with OOP factories, a call to FP factory may fail at runtime if the passed parameter does not correspond to any valid choice known to the factory. We can choose to be explicit about the problem, let the compiler catch us for some cases where it is possible to figure out a problem from the type system, postpone its handling by using an optional type, or hide it inside a null object.
Factory Method
This one seems like a very syntax-sugary thing to me, specific to certain older OOP languages. It is tied to the fact that normal constructors in those languages are always concrete in those languages. Sometimes we want runtime polymorphism to determine what construction action will be taken instead. Factory Method achieves that by allowing to reimplement the method as we inherit from classes.
It should be possible to tie a freestanding function acting as a factory to be a part of any other data type. Functions that have late binding are already virtual, so such a “constructor” method will be acting exactly as Factory Method.
Prototype
First I thought that Prototype is something very OOP specific, even an optimization for cases when we prefer to not construct objects every time by calling constructors.
But after some consideration, I concluded that this may be an important optimization for the FP style. The process of cloning one of pre-stored objects, hidden behind a façade of a function, may be just as important optimization for functional programs.
Given that immutable data types are preferred in FP, the “cloning” step may be implemented as returning a reference to the same pre-configured immutable instance for all cloning requests.
Additionally, Prototype offers polymorphic variation of what actual code will be invoked, while constructors in old OOP languages are usually bound to behavior at compile time. In FP, where a constructor is just another function, it can be passed around, dynamically replaced with another function, and only when invoked, it will determined what it will exactly return. This erases difference between a constructor, a prototype, and factory method.
Builder
This one is quite natural in a functional programming environment. Instead of creating a complex object by passing a long list of its dependencies to some sort of a large constructor method, it is common to start with an empty representation (such as empty list) and incrementally extend it with more data, gradually building the final object. This applies to both pure data types, as well as functions, where closures can be built on top of other closures, “remembering” decisions made by previous steps of construction as closure’s bound parameters.
Adapter
This one is the case of changing the interface to same underlying behavior. The most frequent “interface” in FP is a single callable function or function-like object. Partial application, currying or closures can be chained in order to alter order, number and types of functions’ parameters. Conditional code, pattern matching or calling other functions can be used to remap arguments for arguments incompatible between old and new interfaces.
Bridge
A Bridge is meant to make it easy to combine variations in two or more orthogonal concepts into usable concrete implementations. In the case of OOP, it often means classes and inheritance, and bending them to your will.
The goal of Bridge is to combat the combinatorial explosion of number of classes.
Honestly, this one again looks like a problem caused by overly relying on classes and inheritance, i.e., something from the old OOP languages and habits.
A Bridge solves it by avoiding inheritance and relying on composition and dependency injection.
With first-class functions, dependency injection is certainly usable in FP. Just pass your concrete functions specifying aspects of desirable behavior to a higher-level function that will invoke them when time is right.
Façade
This Pattern adds a simpler interface on top of an object with more complex one.
Similarly to Adapter, FP style code can implement another, simpler interface to existing things.
Decorator
This one is very functional. A majority of invented decorators, written for OOP code, are already applied to methods (i.e., to functions), not to classes (which are groups of functions).
They can be applied to freestanding functions, closures, anonymous functions, any sort of callable, really.
A decorator is that it is a higher-order endomorphic function taking another function and returning a third function.
C = Decorator(A)
What makes it into a decorator is that the signature, or type, of the returned value is the same as the input type. In other words, the returned result can be directly used everywhere the input argument could already be used.
Because C usually “remembers” about A, and oftentimes additional data to
specialize calls to A, there is some state allocation happening
inside Decorator, which means it obtains a flair of creational pattern.
Chain of responsibility
This is similar to Decorator, but instead of decorating functions, we “decorate” data. The chain consists of a group of endomorphic functions, which means that their input domains and output domains are the same.
In a way, we create a pipe operation, where multiple processing steps are functions.
Flyweight
Flyweight is quite popular in implementations of FP data types. Because of immutability, applying an operation cannot directly modify its argument. But what it can do is to return a modified version of its input value to be used later instead of the original one.
This may seem wasteful to do for huge data structures, until one realizes that
nothing forces us to allocate full copies of inputs to be modified and returned.
Instead, both the old and the new values may share most of their contents, only
differing in where “entrypoints” to the actual views are. For example, an
operation of adding a new element Z to an existing list ABCD can return
a new reference to the head, without destroying the original entry point pointing at A:
orig_list ↓
Z -> A -> B -> C -> D -> ø
new_list ↑
This way, both new and old states of the list are still accessible, and the underlying data is not mutated, and no copying was needed. The immutability also means that, if any other piece of code still has references to the same list or its elements, they will not be able to affect anyone else. Any consequent “modification” to the list in fact spawns a new view to the existing data. And of course, no longer reachable views, left outside of active scopes can be garbage-collected.
During an FP program operation many objects derived from each other may in fact be sharing quite a lot of their internal state.
Command
This is essentially what closures of functions over data are equivalent to. A language that supports returning inner functions, either named or anonymous (lambdas), produces closures — an action packaged with data needed to carry out that action.
The traditional OOP command object has its data explicitly stated/copied into it; closures can be more implicit, as the act of capturing the necessary scope is done implicitly by the runtime.
State
A series of closures, each encapsulating current state of the finite state machine, can be used. Each of the closures, when called, returns a new closure that represent the target state of the steps.
Events that initiate the transitions are passed as arguments to the closures.
Note that no mutation of internal state of a single object is needed; instead, state changes are represented by a series of objects creating each other.
Interpreter
This is a very useful pattern when a FP-styled program needs to exhibit interactive behavior. Back-and-forth rounds where data is dynamically entered in the middle of program’s operation do not align well with the “everything is a pure function” approach.
An interpreter of what appears to to be an imperative program, built on top of a pure functional base, is one solution to it. See an example in F# here: https://blog.ploeh.dk/2017/07/11/hello-pure-command-line-interaction/
Proxy
One can think of a Proxy as a Decorator with lazy/conditional instantiation of its wrapped object. Similarly to Decorator, it is quite natural to wrap functions with other functions.
In a language that supports or enforces lazy computation, the whole notion of late creation comes naturally and without need for explicit control of the application code: as long as accessing the wrapped object is not needed, it is not created by the runtime.
Strategy
Because Strategy is simply dynamic polymorphism for a group of related methods, it is easily representable as a group of functions passed together.
Template Method
A higher-order function that takes other functions as parameters and then calls them in fixed order is exactly a Template Method.
Composite
A recursive algorithm that takes both “one” and “many” as valid inputs. This is a quite frequent occurrence in FP-styled programs. The dispatching to concrete behavior is usually explicit, however, i.e., not hidden behind a runtime call to dynamically polymorphic function. Time becomes when it is time to figure out what type the code is dealing with.
Mediator
The Mediator pattern converts an implicit many-to-many relationship network between several objects into an explicit object. In other words, it is an indirection mechanism for message routing.
There is nothing special preventing it from being used in an FP-style program.
Iterator
If we are allowed to have mutable state, then an iterator can be implemented with a closure with mutable state inside. Python’s generators can be an example of such iterator. Repeated calls to seemingly the same function return different results and advance state of a generator.
If we are to strive after strict immutability, then a more natural approach of representing iteration is a series of (tail-)recursive calls. The mutable closure is replaced by a series of immutable closures, each storing state enough to complete its next step of the calculation. Runtime is tasked with keeping the size of saved state in check, i.e. to perform tail-call optimization.
Visitor
There are a few interpretations of Visitor, including dividing it into external and internal, making it less intrusive acyclic, etc. All of them are united in defining it as “ability of adding new operations on elements of an object structure/class hierarchy without modifying existing hierarchy”.
After considering this pattern for some time, I feel that the pattern was designed to overcome constraints of statically typed object-oriented languages of late 20th century. With enough dynamic behavior available in a programming language, the pattern mostly dissolves into higher-level functions taking other functions operating on the same data.
The key to successful design here is to distill an algorithm of traversing the data graph from algorithms executed on individual nodes of that graph. All of that can be carried out in a language that supports higher-level functions.
In addition to that, there are a few essays talking about the relation between the Visitor pattern and algebraic types used in FP:
https://jnkr.tech/blog/visitor-pattern
https://blog.ploeh.dk/2018/06/25/visitor-as-a-sum-type/
Memento
Memento allows to undo previously carried out task domain operations. It is implemented by remembering enough state to perform the rollback and associate it with the operation that has caused those changes.
Just as Command pattern can be modeled with a closure over a function and some data, Memento can be represented by two Commands (do/undo) created at the same time and passed around together. Two similarly related closures can be used just the same way.
If an immutable structure is incrementally built by a program, holding references to its earlier states will provide an alternative rollback mechanism. This is not exactly Memento, but it achieves the same goal.
Observer
This is a pattern which I do not believe to lend itself well to functional programming. The goal of Observer is to simplify management of notifications send to multiple observer objects when their subject has been changed. In other words, it is essential to allow mutation in the system for Observer to be of any use. In FP, this is problematic, undesirable, non-idiomatic, hard-to-implement or impossible, depending on the language.
We can use something else for the same effect. For example, we can repeatedly decorate the mutator function with notifier closures bound to interested observers, so when the resulting callable is invoked, it will invoke those notifiers in (reverse) registration order before (or after) calling the innermost, original function.
Null Object
An object implementing domain-specific empty behavior can be expressed as a function or a tuple of functions doing the same thing. For a client of such code, it will be transparent, as all it does is invoking virtual functions. The goal is to avoid type checks in client code, thus erasing knowledge about types from it.