모노이드에 재귀적으로 취하기

면책 조항: 저는 믹솔로지스트가 아닙니다. 이것은 전문적인 칵테일 조언이 아닙니다!

Sam Horvath-Hunt가 블로그에 . 이것은 제가 확장하고 싶은 FP 모델링의 정말 멋진 예입니다. (Lennart Kolmodin은 Tango의 댄스 스텝이 모노이드를 형성한다고 쓴 적이 있습니다.)

먼저 칵테일 레시피가 재료에 대한 자유 교환 모노노이드라고 가정하여 내 무지를 증명할 것입니다.

재료를 넣는 순서는 상관없어요

칵테일 두 개를 합치면 또 다른 칵테일이 나온다,

아이덴티티 칵테일은 재료가 들어있지 않은 빈 칵테일입니다.

둘째, 재귀적 칵테일 레시피로 수익을 높이고 싶습니다.

이것은 DIKU(University of Copenhagen)의 컴퓨터 공학 학생 리뷰의 스케치에서 가져온 것입니다. Superdrinks (2002); 크레딧은 Uffe Christensen, Uffe Friis Lichtenberg, Jonas Ussing, Niels H. Christensen, Torben Æ에게 돌아갑니다. Mogensen, Jørgen Elgaard Larsen이 스케치를 공동 집필하거나 제정했습니다.

슈퍼 드링크는 다음으로 구성됩니다.

1파트 진,

레몬 2개,

슈퍼 드링크 3부.

이제 스케치에 따르면 이 음료를 구체화하는 나쁜 방법이 많이 있습니다. 그 중 하나는 근사치를 통한 것입니다. 진 1부, 레몬 2부, 슈퍼 드링크의 현재 최상의 근사치인 무엇이든 3부 취하십시오. 이 과정을 충분히 반복하면 점차 더 미세한 슈퍼 드링크를 얻을 수 있습니다.

재귀적으로,

superdrinks(n) = 1 × gin
               + 2 × lemon
               + 3 × superdrinks (n-1)

superdrinks(0)는 물일 수 있습니다. 진이 될 수 있습니다!

약간의 실험,

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)

각 성분의 부품 수 사이의 관계는 재귀를 제거하는 closed form으로 표현할 수 있습니다.

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

(n회 발생하는 3 × 3 × ... 시리즈가 3ⁿ이고, superdrinks(0)보다 항상 1 부분이 적은 레몬이 있으며, 항상 진의 양이 절반이라는 것을 인식함으로써 닫힌 형태를 찾을 수 있습니다. , 또는 recurrence relation 을 풀거나, 함수를 사용하여 세 개의 숫자 시리즈를 확장할 수 있습니다.

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

및 look them up .)

그것은 swifty 얻을 시간입니다.

다음 성분은 진토닉 및 슈퍼 드링크를 만들기에 충분합니다.

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

칵테일은 재료와 그 다양성의 집합입니다.

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

emptyCocktail :: Cocktail
emptyCocktail = Cocktail Map.empty

편의상,

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)

이 모델링의 한 가지 결과는 다음과 같습니다.

> let gintonic = combine (1 `parts` Gin) (2 `parts` Tonic)
> gintonic == combine gintonic gintonic
False

이것들은 칵테일 레시피이기 때문에 레시피에 "진 2부, 토닉 4부"또는 "진 0부"라고 표시되지 않도록 각 재료의 양을 정규화하고 싶습니다.

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

(foldr1 는 partial 이지만 Haskell의 엄격하지 않은 의미 때문에 ingredients 0 번 내에서 사용되기 때문에 Map.map 가 비어 있을 때 평가되지 않습니다.)

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

Eq Cocktail 인스턴스를 normalize 사용하여 c == combine c c for all c 을 사용하도록 전문화하고 싶을 것입니다. 그러나 구조적 평등을 비교할 필요가 있다면 할 수 없지만 정규화에서 평등은 다음과 같이 달성 할 수 있기 때문에 그렇게하고 싶지 않습니다.

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

두 칵테일의 조합이 정규화된 칵테일이 되도록 combine에 정규화를 추가하고 싶을 수도 있습니다. 그러나 이 블로그 게시물은 단일 칵테일에 관한 것이고 combine는 합성 연산자에 대한 최고의 후보이기 때문에 이러한 선택은 실제로 결합 법칙을 위반합니다.

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

따라서 칵테일 레시피를 정규화하는 개념을 좋아하지만 Semigroup Cocktail 인스턴스의 일부로 만드는 것은 훨씬 더 간단한 인스턴스를 남기고 아마도 나쁜 생각일 것입니다.

instance Semigroup Cocktail where
  (<>) = combine

instance Monoid Cocktail where
  mempty = emptyCocktail

슈퍼 드링크의 경우 이제 레시피를 다음과 같이 표현할 수 있습니다.

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

가장 좋은 근사값이 mempty 또는 리뷰 스케치에서 알 수 있듯이 n `parts` Gin 의 밑을 사용하는지 여부는 매우 주관적입니다. 순수 진을 0차 근사값으로 사용하는 슈퍼 드링크의 5차 근사의 경우,

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

건배!