Disclaimer: Jeg er ikke mixolog. Dette er ikke professionel cocktailrådgivning!

Lyt i stedet: Podcast-afsnittet Haskell Weekly, Episode 26: Recursive Monoids.

Jeg læste engang, at man kunne modellere cocktails som monoider.

Det er et virkelig cool eksempel på funktionsorienteret modellering, som jeg gerne vil uddybe.

Først vil jeg demonstrere min uvidenhed og antage, at cocktailopskrifter er frie kommutative monoider over ingredienser:

  • Rækkefølgen hvori du tilføjer ingredienser har ingen betydning,
  • Hvis du kombinerer to cocktails, får du en anden cocktail,
  • Identitetscocktailen er den tomme cocktail uden ingredienser.

Dernæst vil jeg genfortælle en rekursiv cocktailopskrift, som jeg lærte om da jeg studerede datalogi.

Superdrinks

Den kommer fra en DIKU-revysketch fra 2002: Superdrinks; æren tilfalder Uffe Christensen, Uffe Friis Lichtenberg, Jonas Ussing, Niels H. Christensen, Torben Æ. Mogensen, Jørgen Elgaard Larsen, som enten var medforfattere eller opførte sketchen.

En superdrinks består af:

  • 1 del gin,
  • 2 dele citron,
  • 3 dele superdrinks.

Ifølge sketchen er der masser af dårlige måder at materialisere denne drinks på. En særligt katastrofal måde er gennem approksimation: tag 1 del gin, 2 dele citron og 3 dele af hvad der er din nuværende bedste tilnærmelse af superdrinks. Gentag processen tilstrækkeligt mange gange, og du får en gradvist mere nøjagtig superdrinks.

Rekursivt kan man opstille metoden som:

s u p e r d r i n k s ( n ) = + + 1 2 3 × × × g l s i e u n m p o e n r d r i n k s ( n - 1 )

Hvad angår superdrinks(0), kunne det være vand. Men det kunne også være gin!

Prøver vi at sætte konkrete tal på n’s plads kommer følgende ud:

s s u u p p e e r r d d r r i i n n k k s s ( ( 1 2 ) ) = = = + + = 1 1 1 2 3 4 × × × × × × g g g l ( g i i i e 1 i n n n m n o × + + n + g 2 2 i 8 n × × × + l l l e e 2 e m m m o o × o n n n l + + e + m 3 3 o 9 n × × × + s s s u u 3 u p p p e e × e r r r d d s d r r u r i i p i n n e n k k r k s s d s ( ( r ( 0 1 i 0 ) ) n ) k s ( 0 ) )

Forholdet mellem antallet af dele af hver ingrediens kan udtrykkes i lukket form, der eliminerer rekursion:

s u p e r d r i n k s ( n ) = + ( ( 3 3 3 ⁿ ⁿ ⁿ × - - s 1 1 u ) ) p / e 2 × r d × l r e i g m n i o k n n s ( 0 )

Du kan finde den lukkede form enten ved at genkende, at serien 3 × 3 × … med n forekomster er 3ⁿ, at der altid er én del citron mindre end superdrinks(0), og at der altid er halvt så meget gin som det; eller du kan løse deres rekurrensrelation; eller du kan udvide de tre talserier ved brug af en funktion,

> 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])

og slå dem op en, efter, en i talserie-databasen på OEIS.org.

Det er på tide at blive schwifty!

Inden det bliver for abstrakt, skal vi til at kode.

Et godt sprog at programmere med monoider er selvfølgelig Haskell, som er relativt moderne.

Følgende ingredienser er nok til at lave gin-tonic og superdrinks:

data Ingredient = Gin | Tonic | Lemon
  deriving (Eq, Ord, Show)

En cocktail er ethvert sæt ingredienser og deres multiplicitet:

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

emptyCocktail :: Cocktail
emptyCocktail = Cocktail Map.empty

For nemheds skyld er her nogle hjælpefunktioner,

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)

En konsekvens af denne modellering er:

> let gintonic = combine (1 `parts` Gin) (2 `parts` Tonic)
> let double_gintonic = combine gintonic gintonic
> double_gintonic
Cocktail (fromList [(Gin,2),(Tonic,4)])
> gintonic == double_gintonic
False

Kombinerer jeg en opskrift for gin-tonic med sig selv, får jeg ikke en opskrift for gin-tonic. 🤔

Da jeg modellerer opskrifter, vil jeg gerne normalisere mængderne af hver ingrediens.

Ellers ender opskrifterne med at sige “2 dele gin, 4 dele tonic” eller “0 dele 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)

(Bemærk, at selvom foldr1 er partiel, er den på grund af Haskells ikke-strikte semantik aldrig evalueret, når ingredients er tom, fordi den bruges inden for Map.map nul gange, og koden evaluerer derfor sikkert hver gang.)

Demonstration af 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)])

Det ville være fristende at specialisere Eq Cocktail-instansen til at bruge normalize, så c == combine c c for alle c. Men jeg er ikke meget for at gøre det, fordi hvis jeg nogensinde har brug for at sammenligne strukturel lighed, kan jeg ikke, hvorimod lighed under normalisering kan opnås med:

> let (=~) = (==) `on` normalize
> (1 `parts` Gin) =~ (2 `parts` Gin)
True

Det ville også være fristende at tilføje normalisering til combine, så kombinationen af to cocktails er en normaliseret cocktail. Men da blogindlægget her handler om cocktails som monoider, og combine er den bedste kandidat til en kompositionsoperator, bryder et sådant valg faktisk monoiders lov om associativitet:

> 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)])

(Når man kombinerer tre ting, bør det være lige meget om man kombinerer til venstre eller til højre først, men det er ikke sandt når man normaliserer efter hver kombinering.)

Så selvom jeg kan lide tanken om at normalisere cocktailopskrifter, ville det sandsynligvis være en dårlig idé at gøre det til en del af Semigroup Cocktail-instansen, hvilket efterlader de meget enklere typeklasse-instanser:

instance Semigroup Cocktail where
  (<>) = combine

instance Monoid Cocktail where
  mempty = emptyCocktail

Ovenstående rejser spørgsmålet: Er glasset halvt fyldt eller halvt mempty?

Hvad angår superdrinks, kan opskriften nu udtrykkes med kode som:

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

Er den bedste tilnærmelse ved brug af en base af mempty?

Eller, som revysketchen foreslår, n `parts` Gin?

Det handler nok om hvor fuld man ønsker at blive.

For en femte approksimation af superdrinks med ren gin som nulte approksimation,

> normalize . superdrinks 5 $ 1 `parts` Gin
Cocktail (fromList [(Gin,182),(Lemon,121)])

Det kan godt være, vi skal finde nogle større målebægre.

Skål!