FP takes on OOP design patterns tags: pl

modified May 21, 2020.

Visitor Pattern

Objective: Separate an algorithm from the structure on which it works

In Haskell terms, this means defining an ADT implementing Functor. For example: data T a = A | B | C (T a) (T a) deriving Functor.

To call a function f on the data mydata, a client writes:

fmap f mydata

(We’ll assume f is some unsafe function, since the equivalent visit method in Java returns void.)

In Java, the idea is to define an abstract class Data, and have some concrete classes that extend Data, e.g. A, B, C. (This is just Java’s way of making an ADT.)

Then define an interface called DataVisitor defining a visit method overloaded for argument types A, B, and C. (This interface is equivalent to defining and implementing a Functor typeclass specifically for Data.)

Then give each of A, B, C an accept method taking in a DataVisitor, which does nothing but call the DataVisitor’s visit method on itself. (Why define an identical accept method for each of A, B, C? This is Java’s workaround for pattern matching on Data – having each of its subsclasses A, B, C overload some method.)

To call a function f on some mydata, a client needs to do two things. First: define a class FDataVisitor implementing the DataVisitor interface, i.e. defining visit for A, B, C to do whatever f does. (Like for accept, this is akin to pattern matching on the argument of f, and so you need to define a whole class to give f that power). Then, the client creates a FDataVisitor object (call it visitor) and writes:

mydata.accept(visitor)

In summary, the equivalent bits in the Visitor pattern are:

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
abstract `Data` class	${\leftrightarrow}$	ADT type
`A`, `B`, `C`	${\leftrightarrow}$	ADT constructors
`DataVisitor` interface	${\leftrightarrow}$	specialized `Functor` typeclass
`visit`	${\leftrightarrow}$	generic `f` argument to `fmap`
`accept`	${\leftrightarrow}$	`fmap`
`data.accept(f)`	${\leftrightarrow}$	`fmap f data`
`FDataVisitor` class and object	${\leftrightarrow}$	a pattern matching branch in `f`

Interpreter Pattern

Objective: To evaluate an expression in the form of a syntactic tree

In Haskell, this translates to a function (call it eval) which performs pattern matching on an ADT. If a local context is needed, it can be encoded by adding an extra context argument to the function (which is equivalent to using the Reader monad). A global context can be encoded with the State monad.

In Java, this requires defining an Expression interface with an interpret method taking in a global context (local context is not possible). Each terminal and nonterminal in the expression grammar is a class implementing Expression (Java’s way of defining ADTs).

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Expression` interface	${\leftrightarrow}$	ADT type
terminal and nonterminal classes	${\leftrightarrow}$	ADT constructors
`interpret`	${\leftrightarrow}$	a pattern matching branch in `eval`
context	${\leftrightarrow}$	extra argument to `eval`

Command Pattern

Objective: To encapsulate the details of an action to execute it later

In Haskell, each action and its parameters can be encoded as one constructor of an ADT. We can execute it later by writing some eval function that pattern matches and does the corresponding command acting on some global state. Since state is often safely encapsulated by stateful monads like State or IO, you might write your eval in a stateful monad.

Alteratively, you can write each action as its own function, and literally store partially-applied functions for later use. This is easier to write and extend, but harder to debug because you can’t print out functions, and because there is no exhaustiveness checking for invalid commands.

In Java, this is the same as Interpreter pattern, except everything is a nonterminal storing some parameters. These nonterminals can be stored, reordered, etc, any way you want (until they are consumed like in the Interpreter Pattern).

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Command` interface	${\leftrightarrow}$	ADT type
`FooCommand` classes	${\leftrightarrow}$	ADT constructors
`execute`	${\leftrightarrow}$	a pattern matching branch in `eval`
global state, which commands affect	${\leftrightarrow}$	stateful monads

Strategy Pattern

To define a family of algorithms which are interchangeable within the family.

In Haskell this means defining various functions (the algorithms) which are all parameterized by the same variables and functions. This can be accomplished by passing along these parameters as an argument, providing them each time you call each function. But the whole point of the Strategy pattern is to avoid having to do that. Avoiding passing arguments all the time is also the whole point of the State monad.

So, the State monad can be used for the Strategy pattern – every function using this strategy will live in State s where s is some ADT holding the aforementioned parameters. To change the strategy, use put to change the strategy’s variables and functions. Functions using the strategy will use get to get the strategy’s variables and functions.

In Java, this requires our client Context object to store some strategy member variable implementing the Strategy interface, which has data and functions used elsewhere in the methods of Context. Changing the strategy is as easy as setting the strategy member variable.

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Strategy` interface	${\leftrightarrow}$	`s` (ADT for your state)
`Strategy` object	${\leftrightarrow}$	value of type `s`
family of algorithms	${\leftrightarrow}$	the functions living in your `State s` monad
changing the `Strategy`	${\leftrightarrow}$	`put`
accessing the `Strategy`	${\leftrightarrow}$	`get`
methods in `Context`	${\leftrightarrow}$	your API

Adapter Pattern

Objective: To bridge between two incompatible interfaces.

In Haskell, interfaces are typeclasses, so the goal is to let instances of typeclass Foo be used as if they are instances of typeclass Bar. We do this by literally implementing Bar for all instances of typeclass Foo using type variables, like

instance Foo a => Bar a where
  ...

which you might read “Foo anything implies Bar anything”. Then instances of typeclass Foo can directly be used as if they are instances of typeclass Bar.

In Java, this requires writing a FooAdapter class which wraps a Foo but implements the Bar interface. Then Foo objects can be used as a Bar objects by wrapping them in FooAdapter, which is-a Bar.

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
interface	${\leftrightarrow}$	typeclass
`FooAdapter`	${\leftrightarrow}$	(unnecessary)
wrapper variable in `FooAdapter`	${\leftrightarrow}$	type variable

Iterator Pattern

Objective: To traverse elements of a collection without exposing its underlying representation.

In Haskell, we always write collection-traversing operations as some kind of fold, without exception. So the closest equivalent is the Foldable typeclass and its sequential foldr function.

In Java, we write this ‘next’ element function by defining a Iterator interface with a next and hasNext method for traversal. Each collection can define some kind of createIterator method which returns the corresponding CollectionIterator class that implements Iterator.

To use this, the client gets an iterator with createIterator. Then it enters a loop calling hasNext to check if the loop continues, and next to get the next element in sequence.

Java (OOP)	${\leftrightarrow}$	Haskell (FP)
`Iterator` interface	${\leftrightarrow}$	(unnecessary)
`createIterator`	${\leftrightarrow}$	(unnecessary)
code using `Iterator`	${\leftrightarrow}$	some kind of fold
collection with iterators	${\leftrightarrow}$	instance of `Foldable`
`hasNext`	${\leftrightarrow}$	whether the pattern match in `foldr` is base case
`next`	${\leftrightarrow}$	use variable from pattern match in `foldr`

Observer Pattern

Objective: Define a one-to-many relationship between objects such as if one object is modified, it automatically notifies all the depenedent objects.

In Haskell, this is the heart of functional reactive programming (FRP). The gist of it is that updates are Events (a value associated with a time), and states are Behaviors (values that change depending on time, like a signal in signal theory). Everything is done by modifying and combining Behaviors – for example, if it’s true that the engine dies whenever the tank runs out, you’d modify the ‘fuel-in-tank’ Behavior into an engine-is-alive Behavior by applying a function (> 0), exactly like how it is in signal theory.

Whenever updates (Events) happen from the outside, you can turn them into Behaviors and use them to change other Behaviors. And you can always sample a Behavior at interesting times to get Events to act on.

There isn’t a need to keep track of which objects are subscribed or having to call update on each subscribed object, since any potentially interested objects are able to access the state as it exists at every point in time, and are able to define new states from that state based on incoming updates.

In Java, the Observer pattern requires a supervising Subject class which stores a state (with getter and setter) and a collection of Observer objects. It provides an attach method which adds an Observer to the collection. The setter for the state must call the update method of each Observer with the new state.

Observer is an abstract class with a single update method. Classes extending Observer will define update to do whatever interesting thing needs to be done on a state change. Whenever an Observer object is created, it requires a reference to Subject, so the Observer constructor can call subject.attach(this) in order to add the new Observer to the watch list.

TODO: more patterns

References

tagged: pl FP takes on OOP design patterns (permalink) (tweet)
CAGED system for guitar Strategy notes for Chu Shogi