Законы Монад

Добро пожаловать в заключительную часть серии о монадах в Haskell. Сейчас мы уже знаем большишнство идей лежащих в основе зная их тонкости для использования в программах. Но есть еще абстрактные идеи, которые нам нужно изучить, которые связанны со всеми этими структурами. Это записи структурных "законов". Эти правила для typeclass должны выполняться чтобы пересекаться с ожиданиями других программистов.

Жизнь без законов

Помните, что Haskell отражает каждый абстрактный класс с помощью type class. Каждый из этих type class имеет одину или две главные функции. Поэтому, каждый раз реализуя эти функции и её проверки типов, мы получаем функтор/аппликатив/монаду, правильно?

Не совсем. Да, ваша программа будет собираться и у вас будет возможность использовать её объекты. Но это не значит, что ваш объект следует математическим конструктам. Если нет, ваш объект не будет полноценным для других программистов. Каждый type class имеет свои законы. Для примера, давайте вернемся к GovDirectory типу, который мы создавали в статье про функторы. Предположим мы сделали различные объекты функторов:

data GovDirectory a = GovDirectory {
  mayor :: a,
  interimMayor :: Maybe a,
  cabinet :: Map String a,
  councilMembers :: [a]
}

instance Functor GovDirectory where
  fmap f oldDirectory = GovDirectory {
    mayor = f (mayor oldDirectory),
    interimMayor = Nothing,
    cabinet = f <$> cabinet oldDirectory,
    councilMembers = f <$> councilMembers oldDirectory
  }

Насколько видно, это нарушает один из законов функтора. В этом случае, это будет не настоящий функтор. Его поведение должно смущать любого программиста пытающегося его использовать. Мы должны позаботиться о том, чтобы убедиться что наш экземпляр имеет смысл. Как только, вы это почувствуете для type class, значит вы сделали экземпляр по правилу. Не переживайте если вас что-то смущает. Эта статья очень математичка, и вы не сразу поймете, все идеи, что тут предложены. Вы можете понять и использовать эти классы без знания этих законов. Ну что же, окунемся без суеты в эти законы.

Законы функторов

Есть два закона функтороов. Первый - закон идентичности. Мы посмотрим на некотороый вариант этой идеи для каждого из этих type class. Вспомните, как fmap функция работаетс содержанием. Если мы применим нашу функцию идентичности к контейнеру, результатом будет тот же объект.

fmap id = id

Другими словами, наш функтор не должен применять какие-то дополнительные преобразования или сторонние эффекты. Он должен только применять функцию. Второй закон это композиционный. Он гласит, что реализация нашго функтора не должна ломать идею нашей функции.

fmap (g . f) = fmap g . fmap f

-- For reference, remember the type of the composition operator:
(.) :: (b -> c) -> (a -> b) -> (a -> c)

С другой стороы, мы можем собрать две функции, и объединить результат в функции поверх контейнера. С другой стороны, мы применяем первую функцию, получаем результат, и применяем вторую функции поверх. Второй закон говорит, что результаты должны быть одинаковыми. Звучит это сложно. Но вам не нужно переживать. Скорей всего елсли вы сломаете закон композиции в Haskell, скорей всего вы сломаете и закон идентичности.

У нас всего два закона, поэтому двинем дальше.

Аппликативные законы

Аппликативные функторы - это немного сложнее чем кажется. Они имеют 4 различных закона. Первый достаточно просто. Это еще один закон идентичности:

pure id <*> v = v

Слева - обертка для идентичной функции. Затем мы применяем её к контейнеру. Закон аппликативной идентичности говорит, что в результате должен быть тот же объект. Достаточно просто.

Второй закон это закон гомоморфизма. Представим, мы оборачиваем функцию и другие объекты в чистые. Мы можем затем применить обернутую функцию поверх нормального объекта, и затем оберунть их в чистые. Закон гомоморфизма говорит, что эти результаты должны быть одинаковы.

pure f <*> pure x = pure (f x)

Мы должны увидеть чистый шаблон. Поверх этого можно сказать, что большая часть этих законов гласит, что type class это контенеры. Фнукция type class не должна иметь сторонних эффектов. Все они, что они должны - облегчать обертывание, развертывание и проеобразование данных.

Третий закон - закон обмена. Он по-сложнее. Закон говорит, что от порядка оборачивания ничего не должно зависеть. С одной стороны, мы применяем любой аппликтор над обернутым в чистую функцию объектом. С другой - первое мы применяем функцию к объекту как к аргументу. Затем применяем её к первому аппликативу. Должно получиться одно и то же.

u <*> pure y = pure ($ y) <*> u

Последний закон аппликативности, копирует второй закон функтора. Это закон композиции. Он гласит, что композиция функторов не должна влиять на результат.

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

Явное число законов, может быть переполняющим. Однако, экземпляр который вы создадиде скорей всего будет следовать законам. Двигаемся дальше!

Законы монад

У монад есть три закона. Первые два это просто законы идентичности. Как и в прошлые разы.

return a >>= f = f
m >>= return = m

Есть левая и правая части. Они утверждают, что единственное что можно делать функции это оборачивать объект(знакомо?). Нельзя изменять данные как угодно. Главный вывод такой: что ниже приведнный пример кодов одинаков.

func1 :: IO String
func1 = do
  str <- getLine
  return str

func2 :: IO String
func2 = getLine

Третий закон звучит интереснее. Он говорит нам, что асоциативность хранится внутри монад.

(m >>= f) >>= g = m >>= (\x -> f x >>= g)

Но мы видим этот третий закон имеет паралельные структуры с другими композиционными законами. В первом случае, мы применяем две функции в два захода. Во втором случае, мы собирае сначала функцию, и только уже потом применяем результать. Они должны быть одинаковы.

В результате, есть две идеи из всех законов. Первый, идентичность должна сохраняться и в обернутых функциях, как чистых так и в возвращяемых. Второе, функция композиции должна храниться во всех структурах.

Проверка законов.

Как я говорил, большая часть экземпляров, которые вы прошли, будут естественно следовать правилам. С опытом использования различных типо классов, это будет становится правдой. Haskell отличный инструмент проверки ваших экземпляров проходищих определенный закон.

Эта утилита QuickCheck. Она может принимать любое правило, создавать множество разных случаев тестирования в нашем экземпляре функтора GovDirectory. Посмотрим, как QuickCheck доказывает свое начальное падение, и полный успех. Для начала нужно реализовать ти

This utility is QuickCheck. It can take any a certain rule, generate many different test cases on the rule, and verify the rule holds. In this section, we'll run a few tests on our GovDirectory functor instance. We'll see how QuickCheck proves its initial failure, and ultimate success. First we need to implement the Arbitrary type class over our type. We can do this a long as the inner type is also Arbitrary, such as a built-in string type. Then we'll use all the other Arbitrary instances that exist over our inner types:

instance Arbitrary a => Arbitrary (GovDirectory a) where
  arbitrary = do
    m <- arbitrary
    im <- arbitrary
    cab <- arbitrary
    cm <- arbitrary
    return $ GovDirectory
      { mayor = m
      , interimMayor = im
      , cabinet = cab
      , councilMembers = cm
      }

Once you have done that, you can write a test case over a particular rule. In this case, we check the identity function for functors:

main :: IO ()
main = quickCheck govDirectoryFunctorCheck

govDirectoryFunctorCheck :: GovDirectory String -> Bool
govDirectoryFunctorCheck gd = fmap id gd == gd

Now let's test this on the faulty instance we used above. We can see that a particular test will fail:

*** Failed! Falsifiable (after 2 tests):
GovDirectory {mayor = "", interimMayor = Just "\156", cabinet = fromList [("","")], councilMembers = []}

It specifies for us an arbitrary instance that failed the test. Now suppose we correct the instance:

interimMayor = f <$> (interimMayor oldDirectory),

We'll see the tests pass!

+++ OK, passed 100 tests.

SUMMARY

That wraps up our series on monads! Remember that if any of these concepts are still fuzzy, don't hesitate to go back and check out some of the earlier parts of the series. We started by learning the basics about functors, applicative functors and monads. Then we went more in depth on monads and saw some of the more useful ones like the Reader, Writer, and State monads. Then we learned how to combine these together by using monad transformers.

Now that you understand perhaps the most important concept in Haskell, the sky is your limit! Check out our Production Checklist to learn about the many libraries you can use to supercharge your Haskell!