Lambda the Ultimate Pattern Factory

My first programming languages were Lisp, Scheme, and ML. When I later started to work in OO languages like C++ and Java I noticed that idioms that are standard vocabulary in functional programming (fp) were not so easy to achieve and required sophisticated structures. Books like Design Patterns: Elements of Reusable Object-Oriented Software were a great starting point to reason about those structures. One of my earliest findings was that several of the GoF-Patterns had a stark resemblance of structures that are built into in functional languages: for instance the strategy pattern corresponds to higher order functions in fp (more details see below).

Recently, while re-reading through the Typeclassopedia I thought it would be a good exercise to map the structure of software design-patterns to the concepts found in the Haskell type class library and in functional programming in general.

By searching the web I found some blog entries studying specific patterns, but I did not come across any comprehensive study. As it seemed that nobody did this kind of work yet I found it worthy to spend some time on it and write down all my findings on the subject.

I think this kind of exposition could be helpful if you are:

• a programmer with an OO background who wants to get a better grip on how to implement more complex designs in functional programming
• a functional programmer who wants to get a deeper intuition for type classes.
• studying the Typeclassopedia and are looking for an accompanying reading providing example use cases and working code.

This project is work in progress, so please feel free to contact me with any corrections, adjustments, comments, suggestions and additional ideas you might have. Please use the Issue Tracker to enter your requests.

Table of contents

• Lambda the ultimate pattern factory
• The Patternopedia
  • Data Transfer Object → Functor
  • Singleton → Applicative
  • Pipeline → Monad
  • NullObject → Maybe Monad
  • Interpreter → Reader Monad
  <!-- * [? → MonadFail](#--monadfail)-->
  • Aspect Weaving → Monad Transformers
  <!--* [? → MonadFix](#--monadfix) -->
  • Composite → SemiGroup → Monoid
  <!--* [? → Alternative, MonadPlus, ArrowPlus](--alternative-monadplus-arrowplus) -->
  • Visitor → Foldable
  • Iterator → Traversable
  <!-- * [? → Bifunctor](#--bifunctor) -->
  • The Pattern behind the Patterns → Category
  <!--* [? → Arrow](#--arrow) -->
  • Fluent Api → Comonad
• Beyond type class patterns
  • Dependency Injection → Parameter Binding, Partial Application
  • Command → Functions as First Class Citizens
  • Adapter → Function Composition
  • Template Method → type class default functions
  • Creational Patterns
    • Abstract Factory → functions as data type values
    • Builder → record syntax, smart constructor
• Functional Programming Patterns
  • Higher Order Functions
  • Map Reduce
  <!-- * [Continuation Passing](#continuation-passing) -->
  • Lazy Evaluation
  <!-- * [Functional Reactive Programming](#functional-reactive-programming) -->
  • Reflection
• Conclusions
• Some related links

The Patternopedia

The Typeclassopedia is a now classic paper that introduces the Haskell type classes by clarifying their algebraic and category-theoretic background. In particular it explains the relationships among those type classes.

In this chapter I'm taking a tour through the Typeclassopedia from a design pattern perspective. For each of the Typeclassopedia type classes I try to explain how it corresponds to structures applied in software design patterns.

As a reference map I have included the following chart that depicts the Relationships between type classes covered in the Typeclassopedia:

• Solid arrows point from the general to the specific; that is, if there is an arrow from Foo to Bar it means that every Bar is (or should be, or can be made into) a Foo.
• Dotted lines indicate some other sort of relationship.
• Monad and ArrowApply are equivalent.
• Apply and Comonad are greyed out since they are not actually (yet?) in the standard Haskell libraries ∗.

Data Transfer Object → Functor

In the field of programming a data transfer object (DTO) is an object that carries data between processes. The motivation for its use is that communication between processes is usually done resorting to remote interfaces (e.g., web services), where each call is an expensive operation. Because the majority of the cost of each call is related to the round-trip time between the client and the server, one way of reducing the number of calls is to use an object (the DTO) that aggregates the data that would have been transferred by the several calls, but that is served by one call only. (quoted from Wikipedia

Data Transfer Object is a pattern from Martin Fowler's Patterns of Enterprise Application Architecture. It is typically used in multi-layered applications where data is transferred between backends and frontends.

The aggregation of data usually also involves a denormalization of data structures. As an example, please refer to the following diagram where two entities from the backend (Album and Artist) are assembled to a compound denormalized DTO AlbumDTO:

Of course, there is also an inverse mapping from AlbumDTO to Album which is not shown in this diagram.

In Haskell Album, Artist and AlbumDTO can be represented as data types with record notation:

data Album = Album {
    title       :: String
  , publishDate :: Int
  , labelName   :: String
  , artist      :: Artist
} deriving (Show)

data Artist = Artist {
    publicName :: String
  , realName   :: Maybe String
} deriving (Show)

data AlbumDTO = AlbumDTO {
    albumTitle  :: String
  , published   :: Int
  , label       :: String
  , artistName  :: String
} deriving (Show, Read)

The transfer from an Album to an AlbumDTO and vice versa can be achieved by two simple functions, that perfom the intended field wise mappings:

toAlbumDTO :: Album -> AlbumDTO
toAlbumDTO Album {title = t, publishDate = d, labelName = l, artist = a} =
  AlbumDTO {albumTitle = t, published = d, label = l, artistName = (publicName a)}

toAlbum :: AlbumDTO -> Album
toAlbum AlbumDTO {albumTitle = t, published = d, label = l, artistName = n} =
  Album {title = t, publishDate = d, labelName = l, artist = Artist {publicName = n, realName = Nothing}}

In this few lines we have covered the basic idea of the DTO pattern.

Now, let's consider the typical situation that you don't have to transfer only a single Album instance but a whole list of Album instances, e.g.:

albums :: [Album]
albums =
    [
      Album {title = "Microgravity",
             publishDate = 1991,
             labelName = "Origo Sound",
             artist = Artist {publicName = "Biosphere", realName = Just "Geir Jenssen"}}
    , Album {title = "Apollo - Atmospheres & Soundtracks",
             publishDate = 1983,
             labelName = "Editions EG",
             artist = Artist {publicName = "Brian Eno", realName = Just "Brian Peter George St. John le Baptiste de la Salle Eno"}}
    ]

In this case we have to apply the toAlbumDTO function to all elements of the list. In Haskell this higher order operation is called map:

map :: (a -> b) -> [a] -> [b]
map _f []    = []
map f (x:xs) = f x : map f xs

map takes a function f :: (a -> b) (a function from type a to type b) and an [a] list and returns a [b] list. The b elements are produced by applying the function f to each element of the input list. Applying toAlbumDTO to a list of albums can thus be done in the Haskell REPL GHCi as follows:

λ> map toAlbumDTO albums
[AlbumDTO {albumTitle = "Microgravity", published = 1991, label = "Origo Sound", artistName = "Biosphere"},
 AlbumDTO {albumTitle = "Apollo - Atmospheres & Soundtracks", published = 1983, label = "Editions EG", artistName = "Brian Eno"}]

This mapping of functions over lists is a basic technique known in many functional languages. In Haskell further generalises this technique with the concept of the Functor type class.

The Functor class is the most basic and ubiquitous type class in the Haskell libraries. A simple in