Абстрагирование вычислений с помощью классов типов

СТАТЬЯ

Абстрагирование вычислений с помощью классов типов

Из Haskell in Depth Виталия Брагилевского

В этой статье мы обсудим несколько классов типов, возникших в математике (в основном, в абстрактной алгебре и теории категорий).

Получите скидку 40% на Haskell in Depth, введя fccbragilevevsky в поле кода скидки при оформлении заказа на manning.com.

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

Я рекомендую прочитать Typeclassopedia Брента Йорги как блестящее введение в классы типов для абстрагирования вычислений для тех, кто склонен к математике.

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

Как видно на рисунке, выделяются три группы классов типов:

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

Мы обсудим некоторые аспекты этих абстрактных описаний и воспользуемся практическими примерами.

Единственная операция, (‹›)

При использовании этих двух классов типов, Semigroup и Monoid, помните об одном простом правиле — предоставьте общую бинарную операцию над значениями любого типа данных, который определяет их экземпляры. Класс типа Semigroup объявляет такую операцию как:

(<>) :: Semigroup a => a -> a -> a

С ним можно сочетать многое. Например:

ghci> import Data.Semigroup ghci> [1,2,3] <> [4,5,6] [1,2,3,4,5,6] ghci> "Hello " <> "world" "Hello world" ghci> Sum 2 <> Sum 3 Sum {getSum = 5} ghci> Product 2 <> Product 3 Product {getProduct = 6}

Помните, что String является синонимом списка Char, а первые два примера имеют общий экземпляр для списков (и эта операция представляет собой только конкатенацию списков). Третий и четвертый примеры здесь применяют экземпляры, представляющие сложение и умножение — две основные операции над числовыми типами. Они содержат newtype оболочки Sum и Product для любого типа a с экземпляром Num a.

Класс типов Monoid добавляет еще один метод:

mempty :: Monoid a => a

который возвращает нейтральный элемент:

ghci> mempty :: [Int] [] ghci> mempty :: String ""
 ghci> mempty :: Sum Int Sum {getSum = 0}
 ghci> mempty :: Product Int
 Product {getProduct = 1}

Этот элемент называется нейтральным, поскольку ожидается, что он удовлетворяет моноидальным законам, и для любого элемента a:

mempty <> a == a a <> mempty == a

Пустой список, пустое String и числа Sum 0 и Product 1 удовлетворяют этим правилам в отношении соответствующей операции.

В общем, вы бы хотели использовать операцию (<>) для накопления информации, например, при объединении списков и других контейнеров (например, Data.Set или Data.Sequence), объединении свойств конфигурации и тому подобных вещей. Когда вы сталкиваетесь с новым типом данных, всегда полезно поискать предоставленные экземпляры. Если вы видите экземпляры для Semigroup или

Monoid, то вы знаете, что значения этого типа данных можно комбинировать с (<>). Например:

ghci> import Data.Text ghci> :info Text data Text instance Monoid Text -- Defined in 'Data.Text' instance Semigroup Text -- Defined in 'Data.Text'

Наличие этих экземпляров делает возможным следующее:

ghci> :set -XOverloadedStrings ghci> h = "hello" :: Text ghci> c = ", " :: Text ghci> w = ", world" :: Text ghci> h <> c <> w "hello, world"

Другие методы в Semigroup и Monoid вызывают бинарные операции несколько раз:

sconcat :: Semigroup a => Data.List.NonEmpty.NonEmpty a -> a mconcat :: Monoid a => [a] -> a

Обратите внимание на тип Data.List.NonEmpty.NonEmpty в сигнатуре типа sconcat: мы должны использовать его здесь, потому что sconcat понятия не имеет, что возвращать при наличии пустого списка. К счастью, сигнатура типа не позволяет нам запускать его с пустым списком в качестве аргумента. Значение типа NonEmpty должно иметь начало с потенциально пустым хвостом.

Вы можете построить такой список с помощью операции (:|) следующим образом:

ghci> 0 :| [1,2,3] 0 :| [1,2,3] ghci> "x" :| [] "x" :| []

Функция sconcat берет непустой список и применяет (<>) несколько раз, накапливая общее значение. Например:

ghci> sconcat ("x" :| ["y", "z"]) "xyz"

Функция mconcat делает то же самое без этого ограничения, потому что она может возвращать mempty всякий раз, когда ей передается пустой список в качестве аргумента.

Определения классов типов Semigroup и Monoid находятся в стадии разработки. Некоторое время назад у нас было только Monoid; затем было добавлено Semigroup, но в то время не было прямых связей между этими двумя классами. В GHC версии 8.4 Semigroup стал надклассом Monoid. Если вы посмотрите на их определения, скорее всего, вы увидите следы их истории, такие как метод mappend, который совпадает с (<>). Ожидается, что этот метод mappend будет удален из класса типов Monoid в будущем. Полную информацию об этом плане можно прочитать здесь: https://prime.haskell.org/wiki/Libraries/Proposals/SemigroupMonoid.

Отображение, применение и упорядочивание в вычислительном контексте

Давайте разберем название этого подраздела. Мерриам-Вебстер дает следующее определение контекста: взаимосвязанные условия, в которых что-то существует или происходит.

вычислительный контекст означает, что эти взаимосвязанные условия возникли в процессе вычислений. В Haskell вы можете использовать множество различных вычислительных контекстов: некоторые из них позволяют иметь побочные эффекты, такие как ввод/вывод (IO) или изменяемые переменные (State, ST), а другие поддерживают идею вычислений с потенциальным отсутствием результат (Maybe, Either) или с возможностью сохранения дополнительной информации вместе с вычислением (Writer). Вероятно, вы сталкивались с некоторыми из них, когда начинали изучать Haskell.

Все эти контексты имеют общее абстрактное поведение, позволяя вам сопоставлять, применять и упорядочивать их. Это поведение определяется тремя классами типов с причудливыми именами:

Functor абстрагирует отображение некоторого значения в вычислительном контексте.
Applicative позволяет применять функцию в контексте к значению в контексте и вставлять значение в контекст.
Monad позволяет упорядочивать вычисления в контексте, чтобы структурировать то, что делается в следующем вычислении, в зависимости от результата предыдущего.

Эта формулировка представляет собой текстовое представление сигнатур типов для следующих методов:

fmap :: Functor f => (a -> b) -> f a -> f b pure :: Applicative f => a -> f a (<*>) :: Applicative f => f (a -> b) -> f a -> f b
 (>>=) :: Monad m => m a -> (a -> m b) -> m b

Хотя эти три класса типов также определяют и другие методы (вы можете изучить их с помощью команды :info GHCi), они наиболее важны для понимания того, что здесь происходит. Мы часто называем контексты функциональными, аппликативными или монадическими, если существует соответствующий экземпляр и мы хотим указать конкретное свойство.

Слова значение в контексте относятся к сигнатурам типов f a или m a, где a — тип значения (результат вычисления), а f или m ограничивает контекст. Точно так же f (a → b) — это функция в контексте. Взгляните также на второй аргумент в сигнатуре типа (>>=), (a → m b) — это то, что подразумевается под «следующее вычисление зависит от результата предыдущего» (мы называем его монадической функцией). . По этой причине некоторые называют монады «программируемой точкой с запятой».

Когда вы смотрите на конкретные контексты, эти методы конкретизируются и иногда выглядят совершенно по-разному, но все они реализуют одни и те же идеи отображения, применения и последовательности.

Вы можете найти множество вводных материалов по этим трем классам типов — в Typeclassopedia есть много ссылок, а в Разделе 5 книги Get Programming with Haskell Уилла Курта (Мэннинга) они подробно описаны. детали практическим способом — и я не буду пытаться повторять их. Вместо этого я приведу вам примеры трех разных контекстов и операций над значениями в них, чтобы убедиться, что мы находимся на одной странице.

Параллельное изучение разных контекстов

Классы типов, о которых мы говорим, имеют общие представления о поведении. Всегда поучительно идти обоими путями, от общих идей к конкретным реализациям и наоборот. В этом подразделе рекомендуется идти по пути понимания от частных примеров к общим понятиям. Мы сосредоточимся на этих трех контекстах:

IO, что позволяет делать ввод/вывод
Writer, который поддерживает протоколирование дополнительной информации в процессе вычислений (вы можете получить доступ к этому контексту после импорта модуля Control.Monad.Writer)
[] (список), что является наиболее необычным контекстом недетерминированных вычислений.

Во-первых, давайте рассмотрим несколько примеров того, что такое значение в контексте:

getLine :: IO String — это значение типа String в контексте, который отвечает за его получение из побочного эффекта чтения пользовательского ввода.
writer (42, "step 1\n") :: Writer String Int — это значение 42 типа Int, которое сопровождается журналом "step 1\n" в форме String.
[1,2,3] :: [Int] — это одно из значений 1, 2 или 3 типа Int, но мы не уверены, какое из них является результатом вычислений (эту неопределенность я называю недетерминизмом).

Теперь проверим отображение методом fmap из класса типов Functor:

ghci> fmap (++"!") getLine Hi
 "Hi!"

Вторая строка, Hi, представляет собой пользовательский ввод, который становится значением в контексте во время выполнения, а последняя строка является результатом сопоставления (++"!") с этим результатом.

А как насчет Writer? Взглянем:

ghci> fmap (+1) (writer (42, "step 1\n")) :: Writer String Int WriterT (Identity (43,"step 1\n"))

Помимо выходного беспорядка с WriterT и Identity, вы можете ясно видеть новое значение 43 (результат отображения (+1) на 42) в неизмененном контексте — журнал не меняется. Что касается третьего контекста:

ghci> fmap (+1) [1,2,3] [2,3,4]

У нас есть одно из значений 2, 3 или 4, каждое из которых является потенциальным результатом недетерминированного отображения (+1) на 1, 2 или 3. Понятно, что это обычный map для списков.

На следующем шаге мы хотели бы рассмотреть эти контексты в аппликативном контексте, чтобы попытаться увидеть какие-либо сходства:

ghci> pure (++) <*> getLine <*> getLine hello world "helloworld"
 ghci> pure (+) <*> writer (42, "step 1\n") <*> writer (10, "step 2\n") :: Writer String Int WriterT (Identity (52,"step 1\nstep 2\n")) ghci> pure (+) <*> [1,2,3] <*> [4,5,6]
 [5,6,7,6,7,8,7,8,9]

У нас есть функция с двумя аргументами, которая вводится в контекст, а затем применяется к двум значениям в контексте, и мы ясно видим результаты применения "helloworld", 52 или одного из значений в списке [5,6,7,6,7,8,7,8,9]. Мы также можем видеть, что контекст выполняет свою работу, получая два пользовательских ввода, комбинируя журналы и используя недетерминизм (у нас было три потенциальных результата для первого значения в контексте и три потенциальных результата для второго значения в контексте, и мы получили девять (=3*3) из них наконец).

Давайте посмотрим на (>>=), названный «bind» для нашего последнего примера здесь:

ghci> getLine >>= putStrLn hello hello
 ghci> writer (42, "step 1\n") >>= (\a -> writer (a+1, "step 2\n"))  :: Writer String Int WriterT (Identity (43,"step 1\nstep 2\n")) ghci> [1,2] >>= (\x -> [x-1, x, x+1])
 [0,1,2,1,2,3]

Попробуйте сами разобраться, что здесь сделано с результатом первого вычисления и как раскрываются контексты. Не забудьте проверить тип (>>=), прежде чем начать думать.

сделать запись

Нотация do представляет собой удобный синтаксический механизм для выражения монадических вычислений, который включает в себя:

Последовательность операций путем их написания одна за другой (как в императивных языках программирования)
Привязка значений в контексте к именам с ←
Построение последующих операций с именами, связанными ранее (это основная особенность класса типа Monad)

Например, следующий код:

action t = do   a <- f t
   b <- g a
   h a
   return (k a b)

обесахаривается на:

action t =   f t >>= \a ->
 a >>= \b ->
 a >>
   return (k a b)

что эффективно:

action t = f t >>= \a -> g a >>= \b -> h a >> return (k a b)

Линеаризованные определения, подобные этому, почти невозможно читать и неудобно писать; Обозначение do очень помогает.

Обратите внимание, что вы можете использовать нотацию do в любом монадическом контексте. Например, следующие три фрагмента абсолютно законны. Первый контекст IO:

readNumber :: IO Int readNumber = do   s <- getLine
   return (read s)

Второй — Writer, где мы рекурсивно вычисляем сумму чисел от 0 до n и протоколируем все промежуточные аргументы (логирование осуществляется через вспомогательную функцию tell из Control.Monad.Writer):

sumN :: Int -> Writer String Int sumN 0 = writer (0, "finish") sumN n = do   tell (show n ++ ",")
   s <- sumN (n-1)
   return (n + s)

Запуск этой функции в GHCI дает:

ghci> sumN 5 WriterT (Identity (15,"5,4,3,2,1,finish"))

Здесь вы можете видеть, что вычисления привели к числу 15, а также предоставлен полный журнал.

Некоторые монады поддерживают раннеры, функции, которые предоставляют развернутые результаты. В случае Writer у нас есть функция runWriter, которая возвращает пару (result, log):

ghci> runWriter (sumN 5) (15,"5,4,3,2,1,finish")

Третий контекст представляет собой список:

cartesianProduct  :: [Int] -> [Int] -> [(Int, Int)] cartesianProduct xs ys = do   x <- xs
   y <- ys
   return (x, y)

Мы можем применить функцию cartesianProduct к некоторым спискам и увидеть результаты в следующем сеансе GHCi:

ghci> cartesianProduct [1..2] [1..3] [(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)]

Каждый do-блок соответствует ровно одному монадическому контексту, поучительно понимать, с каким Monad вы работаете в каждый момент времени, так как от этого в решающей степени зависят наблюдаемые результаты. Распространенной ошибкой является ожидание чего-то, что не обрабатывается используемым контекстом.

Нотация do разлагается на следующие монадические операции:

(>>=) :: Monad m => m a -> (a -> m b) -> m b
 (>>) :: Monad m => m a -> m b -> m b

где последняя операция, (>>), представляет собой упрощенную версию (>>=), не зависящую от результата предыдущего вычисления. Вы можете найти подробности о десахаризации нотации do в Typeclassopedia (https://wiki.haskell.org/Typeclassopedia#do_notation) и во многих других источниках.

Складывание и перемещение

Последние два класса — Foldable и Traversable — оба отражают идею обработки контейнера, набора значений с различными возможностями.

Любой экземпляр Foldable должен реализовывать один из следующих методов:

class Foldable (t :: * -> *) where   foldMap :: Monoid m => (a -> m) -> t a -> m
   foldr :: (a -> b -> b) -> b -> t a -> b   ...

Оба они должны перебирать t a, контейнер t с элементами типа a, обрабатывать каждый элемент и объединять все результаты. Foldable содержит шестнадцать методов. Около половины из них составляют разного рода фальцовки, а именно обработка элементов тары с помощью специфических операций; другие включают length, elem и maximum. Все они когда-то были методами списка, которые позже были обобщены для поддержки других контейнеров.

Класс типов Traversable одновременно проще (у него всего четыре метода, причем два из них повторяют два других в более богатом контексте, существуя только по историческим причинам), и сложнее за счет объединения эффектов Functor, Applicative, Monad и Foldable . Это определение Traversable:

class (Functor t, Foldable t) => Traversable (t :: * -> *) where   traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
   sequenceA :: Applicative f => t (f a) -> f (t a)
   mapM :: Monad m => (a -> m b) -> t a -> m (t b)
   sequence :: Monad m => t (m a) -> m (t a)
   {-# MINIMAL traverse | sequenceA #-}

Метод traverse перебирает каждый элемент в контейнере (второй аргумент) и эффективно применяет свой первый аргумент к элементу, как в Applicative f. Из-за ограничений на t и f действия, выполняемые в traverse, сильно зависят от конкретных экземпляров, и говорить об этом в целом сложно.

Давайте рассмотрим простой пример. Из сигнатуры типа метода traverse видно, что ему требуются два аргумента: функция a → f b, возвращающая значение в аппликативном контексте, и контейнер t a элементов типа a. Возьмем список значений Int в качестве контейнера и IO в качестве аппликативного контекста. Затем нам нужна функция, возвращающая значение в IO, например:

addNumber :: Int -> IO String
 addNumber n = pure (++) <*> pure (show n ++ " ")  <*> getLine

Тип этой функции совместим с traverse: она берет число, превращает его в String и объединяет его со строкой, введенной пользователем. Теперь мы готовы увидеть traverse в действии:

ghci> traverse addNumber [1..5] aaa bbb ccc ddd eee
 ["1 aaa","2 bbb","3 ccc","4 ddd","5 eee"]

Здесь я ввел пять строк, а затем пронумеровал их. Всегда полезно проверить типы:

ghci> :t traverse addNumber [1..5] traverse addNumber [1..5] :: IO [String]

У нас есть список String в контексте IO, и этот конкретный вызов traverse имеет тип:

(a   -> f  b)      -> t a   -> f  (t b)
    (Int -> IO String) -> [Int] -> IO [String]

Модуль Data.Foldable предоставляет traverse_ функцию, аналогичную traverse, которая не собирает результаты отдельных вычислений:

traverse_  :: (Applicative f, Foldable t) => (a -> f b) -> t a -> f ()

Всегда следуйте типам; они очень помогают вам в понимании абстрактных функций. Попробуйте использовать тот же подход для sequenceA: выберите любой контейнер (возьмите список как самый простой; Maybe тоже работает) и любой аппликативный контекст (попробуйте Writer!), а затем создайте вызов sequenceA. Вы обязательно увидите, что там происходит.

Написание кода с учетом Foldable и Traversable, в отличие от использования определенного контейнера или структуры данных, позволяет вам изменять контейнер в любое время.

В результате вы можете повысить эффективность своего кода, не переписывая его.

Если вы хотите увидеть больше, ознакомьтесь с книгой на платформе Мэннинга liveBook здесь.

Абстрагирование вычислений с помощью классов типов

СТАТЬЯ