Списки

Списки (на самом деле конструктор типа списка, []) являются аппликативными функторами. Вот так сюрприз! Вот как [] является экземпляром класса Applicative:

instance Applicative [] where

   pure x = [x]

   fs <*> xs = [f x | f <– fs, x <– xs]

Вспомните, что функция pure принимает значение и помещает его в контекст по умолчанию. Другими словами, она помещает его в минимальный контекст, который всё ещё возвращает это значение. Минимальным контекстом для списков был бы пустой список, но пустой список означает отсутствие значения, поэтому он не может содержать в себе значение, к которому мы применили функцию pure. Вот почему эта функция принимает значение и помещает его в одноэлементный список. Подобным образом минимальным контекстом для аппликативного функтора Maybe было бы значение Nothing – но оно означает отсутствие значения вместо самого значения, поэтому функция pure в реализации экземпляра для типа Maybe реализована как вызов конструктора данных Just.

Вот функция pure в действии:

ghci> pure "Эй" :: [String]

["Эй"]

ghci> pure "Эй" :: Maybe String

Just "Эй"

Что насчёт оператора <*>? Если бы тип оператора <*> ограничивался только списками, мы получили бы (<*>) :: [a –> b] –> [a] –> [b]. Этот оператор реализован через генератор списков. Он должен каким-то образом извлечь функцию из своего левого параметра, а затем с её помощью отобразить правый. Но левый список может не содержать в себе функций или содержать одну либо несколько функций, а правый список также может содержать несколько значений. Вот почему мы используем генератор списков для извлечения из обоих списков. Мы применяем каждую возможную функцию из левого списка к каждому возможному значению из правого. Результирующий список содержит все возможные комбинации применения функции из левого списка к значению из правого.

Мы можем использовать оператор <*> со списками вот так:

ghci> [(*0),(+100),( 2)] <*> [1,2,3]

[0,0,0,101,102,103,1,4,9]

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

В следующем примере применяются две функции между двумя списками:

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

[4,5,5,6,3,4,6,8]

Оператор <*> левоассоциативен, поэтому сначала выполняется [(+),(*)] <*> [1,2], результатом чего является такой же список, как [(1+),(2+),(1*),(2*)], потому что каждая функция слева применяется к каждому значению справа. Затем выполняется [(1+),(2+),(1*),(2*)] <*> [3,4], что возвращает окончательный результат.

Как здорово использовать аппликативный стиль со списками!

ghci> (++) <$> ["хa","хeх","хм"] <*> ["?","!","."]

["хa?","хa!","хa.","хeх?","хeх!","хeх.","хм?","хм!","хм."]

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

Вы можете воспринимать списки как недетерминированные вычисления. Значение вроде 100 или "что" можно рассматривать как детерминированное вычисление, которое имеет только один результат. В то же время список вроде [1,2,3] можно рассматривать как вычисление, которое не в состоянии определиться, какой результат оно желает иметь, поэтому возвращает нам все возможные результаты. Поэтому когда вы пишете что-то наподобие (+) <$> [1,2,3] <*> [4,5,6], то можете рассматривать это как объединение двух недетерминированных вычислений с помощью оператора + только для того, чтобы создать ещё одно недетерминированное вычисление, которое ещё меньше уверено в своём результате.

Использование аппликативного стиля со списками часто является хорошей заменой генераторам списков. В главе 1 мы хотели вывести все возможные комбинации произведений [2,5,10] и [8,10,11] и с этой целью предприняли следующее:

ghci> [x*y | x <– [2,5,10], y <– [8,10,11]]

[16,20,22,40,50,55,80,100,110]

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

ghci> (*) <$> [2,5,10] <*> [8,10,11]

[16,20,22,40,50,55,80,100,110]

Для меня такой подход более понятен, поскольку проще понять, что мы просто вызываем оператор * между двумя недетерминированными вычислениями. Если бы мы захотели получить все возможные произведения элементов, больших 50, мы бы использовали следующее:

ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]

[55,80,100,110]

Легко увидеть, что вызов выражения pure f <*> xs при использовании списков эквивалентен выражению fmap f xs. Результат вычисления pure f – это просто [f], а выражение [f] <*> xs применит каждую функцию в левом списке к каждому значению в правом; но в левом списке только одна функция, и, следовательно, это похоже на отображение.