DEV Community

Simon Shine
Simon Shine

Posted on • Updated on

Getting recursively drunk with monoids

#haskell #monoids

Disclaimer: I am not a mixologist. This is not professional cocktail advice!

Sam Horvath-Hunt blogged about modelling cocktails as monoids. This is a really cool example of FP modelling that I want to expand on. (Lennart Kolmodin once wrote that the dance steps of Tango form a monoid.)

First, I will demonstrate my ignorance by assuming that cocktail recipes are free commutative monoids over ingredients:

  • The order in which you add ingredients does not matter,
  • If you add two cocktails together, you get another cocktail,
  • The identity cocktail is the empty cocktail with no ingredients in it.

Second, I want to up the ante with a recursive cocktail recipe.

It comes from a sketch in the computer science student revue at DIKU (University of Copenhagen): Superdrinks (2002); credits go to Uffe Christensen, Uffe Friis Lichtenberg, Jonas Ussing, Niels H. Christensen, Torben Æ. Mogensen, Jørgen Elgaard Larsen who either co-wrote or enacted the sketch.

A superdrinks consists of:

  • 1 part gin,
  • 2 parts lemon,
  • 3 parts superdrinks.

Now, according to the sketch there are plenty of bad ways to materialize this drink; one such is through approximation: take 1 part gin, 2 parts lemon and 3 parts of whatever is your current best approximation of superdrinks. Iterate this process enough times and you will have a gradually finer superdrinks.

Recursively,

superdrinks(n) = 1 × gin
               + 2 × lemon
               + 3 × superdrinks (n-1)
Enter fullscreen mode Exit fullscreen mode

As for superdrinks(0), it could be water. It could be gin!

Experimenting a little,

superdrinks(1) = 1 × gin + 2 × lemon + 3 × superdrinks(0)

superdrinks(2) = 1 × gin + 2 × lemon + 3 × superdrinks(1)
               = 1 × gin
               + 2 × lemon
               + 3 × (1 × gin + 2 × lemon + 3 × superdrinks(0))
               = 4 × gin + 8 × lemon + 9 × superdrinks(0)
Enter fullscreen mode Exit fullscreen mode

The relationship between the number of parts of each ingredient can be expressed in closed form eliminating recursion:

superdrinks(n) = (3ⁿ - 1)/2 × gin
               + (3ⁿ - 1) × lemon
               + 3ⁿ × superdrinks(0)
Enter fullscreen mode Exit fullscreen mode

(You can find the closed form either by recognizing that the series 3 × 3 × ... with n occurrences is 3ⁿ, that there's always one less part lemon than superdrinks(0), and that there's always half the amount of gin of that; or you can solve their recurrence relation; or you can expand the three number series using a function,

> let superdrinks (gin, lemon, super) = (1 + 3*gin, 2 + 3*lemon, 3*super)
> unzip3 $ take 6 $ iterate superdrinks (0,0,1)
([0,1,4,13,40,121],[0,2,8,26,80,242],[1,3,9,27,81,243])
Enter fullscreen mode Exit fullscreen mode

and look them up.)

It is time to get schwifty.

The following ingredients are enough to make gin-tonic and superdrinks:

data Ingredient = Gin | Tonic | Lemon
  deriving (Eq, Ord, Show)
Enter fullscreen mode Exit fullscreen mode

A cocktail is any set of ingredients and their multiplicity:

newtype Cocktail = Cocktail (Map Ingredient Natural)
  deriving (Eq, Ord, Show)

emptyCocktail :: Cocktail
emptyCocktail = Cocktail Map.empty
Enter fullscreen mode Exit fullscreen mode

For convenience,

parts :: Natural -> Ingredient -> Cocktail
parts n ingredient =
  Cocktail (Map.singleton ingredient n)

combine :: Cocktail -> Cocktail -> Cocktail
combine (Cocktail c1) (Cocktail c2) =
  Cocktail (Map.unionWith (+) c1 c2)
Enter fullscreen mode Exit fullscreen mode

One consequence of this modelling is:

> let gintonic = combine (1 `parts` Gin) (2 `parts` Tonic)
> gintonic == combine gintonic gintonic
False
Enter fullscreen mode Exit fullscreen mode

Since these are cocktail recipes, I'd like to normalize the quantities of each ingredient so that recipes don't eventually say "2 parts gin, 4 parts tonic" or "0 parts gin":

normalize :: Cocktail -> Cocktail
normalize (Cocktail ingredients) =
  Cocktail . normalize' $ ingredients
  where
    scale = foldr1 gcd (Map.elems ingredients)
    normalize' = Map.map (`div` scale) . Map.filter (/= 0)
Enter fullscreen mode Exit fullscreen mode

(Note that while foldr1 is partial, because of Haskell's non-strict semantics, it is never evaluated when ingredients is empty because it is used within Map.map zero times.)

Demonstrating normalize:

> normalize emptyCocktail 
Cocktail (fromList [])

> normalize (0 `parts` Gin)
Cocktail (fromList [])

> normalize $ combine (2 `parts` Gin) (4 `parts` Tonic)
Cocktail (fromList [(Gin,1),(Tonic,2)])
Enter fullscreen mode Exit fullscreen mode

It would be tempting to specialize the Eq Cocktail instance to use normalize so that c == combine c c for all c. But I don't like to do that because if you ever need to compare for structural equality, you can't, whereas equality under normalization can be achieved with:

> let (=~) = (==) `on` normalize
> (1 `parts` Gin) =~ (2 `parts` Gin)
True
Enter fullscreen mode Exit fullscreen mode

It would also be tempting to add normalization to combine so that the combination of two cocktails is a normalized cocktail. But since this blog post is about monoidal cocktails and combine is the best candidate for a composition operator, such choice actually breaks the law of associativity:

> let norm_combine c1 c2 = normalize (combine c1 c2)

> gin1 `norm_combine` (gin1 `norm_combine` tonic1)
Cocktail (fromList [(Gin,2),(Tonic,1)])

> (gin1 `norm_combine` gin1) `norm_combine` tonic1
Cocktail (fromList [(Gin,1),(Tonic,1)])
Enter fullscreen mode Exit fullscreen mode

So while I like the notion of normalizing cocktail recipes, making it a part of the Semigroup Cocktail instance would probably be a bad idea, leaving the much simpler instances:

instance Semigroup Cocktail where
  (<>) = combine

instance Monoid Cocktail where
  mempty = emptyCocktail
Enter fullscreen mode Exit fullscreen mode

This begs the question: Is the glass half full or half mempty?

As for superdrinks, the recipe can now be expressed as:

superdrinks :: Natural -> Cocktail -> Cocktail
superdrinks n base = mconcat
  [ ((3^n - 1) `div` 2) `parts`  Gin
  ,  (3^n - 1)          `parts`  Lemon
  ,  (3^n)              `rounds` base
  ]

rounds :: Natural -> Cocktail -> Cocktail
rounds n = mconcat . genericReplicate n
Enter fullscreen mode Exit fullscreen mode

Whether the best approximation is using a base of mempty or, as the revue sketch suggests, n `parts` Gin, is highly subjective. For a 5th approximation of superdrinks using pure gin as 0th approximation,

> normalize $ superdrinks 5 (1 `parts` Gin)
Cocktail (fromList [(Gin,182),(Lemon,121)])
Enter fullscreen mode Exit fullscreen mode

Cheers!

Latest comments (3)

Collapse
 
tfausak profile image
Taylor Fausak •

Great post! We liked it so much we recorded a podcast about it :) haskellweekly.news/episode/26.html

Collapse
 
ysangkok profile image
Janus Troelsen •

You joke around that 2 gallons of gin is so much. But a "part" is not an actual physical unit, is it? I thought it only is a fraction, constructed using the other parts.

Also, the 21 year age limit does not apply to Simon since he is not US-American.

Ok, maybe I am taking the podcast too literally :P

Collapse
 
sshine profile image
Simon Shine •

Ha, I just realized.

Thanks for making new podcast episodes again. :)

Read next

driver3229 profile image

Cannot render components after the Fetch() call.

Rahul3229 -

mqtri profile image

Hello world

mqtri -

philipjohnbasile profile image

Leveraging Angular DevTools for Enhanced Development Efficiency

Philip John Basile -

anmolbaranwal profile image

🚀 21 Tools to take your dev skills to the moon 🌝

Anmol Baranwal -