ГЛАВА ПОКА ДАЛЕКА ОТ ЗАВЕРШЕНИЯ
В этой главе мы поговорим об особенностях конструкторов типов (или, как ещё их называют, параметрических типов) наподобие Maybe, IO или State. Предмет обсуждения этой главы сильно выходит за рамки языка Haskell и актуален для большинства языков со статической типизацией (а кроме того, даже более актуален для языков с динамической типизацией, поскольку предоставляет практически полезные способы структурирования кода).
Функцию a->b можно рассматривать как некий способ модификации объекта типа a, изменяющий его таким образом, что он приобретает тип b. Будем говорить, что любой объект обладает функциональным интерфейсом.
Помимо функционального интерфейса очень часто встречается моноидальный интерфейс: модификация объекта типа a при помощи другого объекта типа a. Например: (++) для списков, (+) для чисел, (*) для чисел, (.) для функций типа x->x.
Нетрудно заметить, что для каждого из этих интерфейсов есть тривиальный модификатор, оставляющий объект неизменным:
-- под знаком "равно" ниже понимается какого-нибудь рода эквивалентность
[] ++ x = x -- глубокая нормальная эквивалентность
0 + x = x -- нормальная эквивалентность
1 * x = x -- нормальная эквивалентность
id . f = f -- экстенсиональная эквивалентностьБолее того, в каждом из этих случаев моноидальная операция осуществляет композицию модификаторов:
(m ++ n) ++ x = m ++ (n ++ x)
(m + n) + x = m + (n + x)
(m * n) * x = m * (n * x)
(m . n) . f = m . (n . f)Фиксируем тип a, объект mempty :: a и операцию (<>) :: a -> a -> a. Будем говорить, что они образуют моноид, если выполняются эквивалентности:
mempty <> x = x
(m <> n) <> x = m <> (n <> x)Заметим, что согласно второму свойству m <> mempty и m экстенсионально эквивалентны как модификаторы. Зачастую требуют их полной эквивалентности (в том же смысле, что и для m и mempty <> m).
В языке Haskell есть стандартный модуль Data.Monoid, в котором определён класс Monoid, а также – моноидальная структура для большого количества разных типов. Вы можете попробовать следующие выражения в интерпретаторе (не забыв сделать import Data.Monoid)
Sum 3 <> Sum 4 <> Sum 5
Product 3 <> Product 4 <> Product 5
[1,2,3] <> [4,5,6]
"foo" <> "bar" <> "baz"
mempty :: Sum Integer
mempty :: Product DoubleПусть c – некоторый однопараметрический конструктор типа: это означает, что для любого типа x выражение c x означает некоторый тип. Примером c может служить Maybe, IO, ([]), (,) a, (->) a State a. Величину типа c x будем называть сложным объектом на основе типа x.
Под модификацией сложного объекта типа c a мы будем понимать преобразование его в объект типа c b. На практике чаще всего встречаются четыре интерфейса для модификации сложных объектов:
a -> b;c (a -> b);a -> c b;c a -> b.Например, для списков есть общепринятые интерфейсы всех четырёх видов:
f <$> [] = []
f <$> (x:xs) = f x : (f <$> xs)
[] <*> l = []
(f:fs) <*> l = (f <$> l) ++ (fs <*> l)
f =<< [] = []
f =<< (x:xs) = f x ++ (f =<< xs)
f <<= [] = undefined
f <<= [x] = [x]
f <<= (x:xs) = f (x:xs) : (f <<= xs)К каждому из этих интерфейсов обычно прилагается тривиальный модификатор, оставляющий сложный объект неизменным:
id = \x -> x;c (a -> a) (далее – aid);a -> c a (далее – pure);c a -> a (далее – extract).Для вышеприведённых интерфейсов к спискам тривиальные модификаторы определены так:
aid = [id]
pure x = [x]
extract [] = undefined
extract (x:xs) = xВ РАЗРАБОТКЕ
В этом разделе описаны различные интерфейсы к однопараметрическим типам. Для каждого интерфейса дана простая реализация, а также указано, где найти и как пользоваться общепринятой реализацией.
Величина типа a с параметром типа p – это просто отображение типа p -> a.
type Param p a = p -> a
-- функториальный интерфейс
(<$>) :: (a -> b) -> Param p a -> Param p b
f <$> v = f . v
-- аппликативный интерфейс
(<*>) :: Param p (a -> b) -> Param p a -> Param p b
f <*> v = \x -> (f x) (v x)
aid :: Param p (a -> a)
aid = const id
-- монадный интерфейс (общий параметр у цепочки параметризованных преобразований)
(=<<) :: (a -> Param p b) -> Param p a -> Param p b
f =<< v = \x -> f (v x) x
pure :: a -> Param p a
pure = const
ask :: Param p p
ask = id
-- комонадный интерфейс (модификация величины на основе значений в окрестности параметра)
(<<=) :: Monoid p => (Param p a -> b) -> Param p a -> Param p b
f <<= v = \x -> f (\y -> v $ y <> x)
extract :: Monoid p => Param p a -> a
extract v = v mempty
shift :: p -> Param p a -> a
shift x v = v xВ РАЗРАБОТКЕ
Величина типа a, аугментированная величиной типа s, – это пара типа (a,s).
type Aug s a = (a,s)
-- функториальный интерфейс
(<$>) :: (a -> b) -> Aug s a -> Aug s b
f <$> (x,z) = (f x, z)
-- аппликативный интерфейс
(<*>) :: Monoid s => Aug s (a -> b) -> Aug s a -> Aug s b
(f,y) <*> (x,z) = (f x, y <> z)
aid :: Monoid s => Aug s (a -> a)
aid = (id, mempty)
-- монадный интерфейс (композиция аугментаций)
(=<<) :: Monoid s => (a -> Aug s b) -> Aug s a -> Aug s b
f =<< (x,z) = case f x of
(g,y) -> (g, y <> z)
pure :: Monoid s => a -> Aug s a
pure x = (x, mempty)
tell :: s -> Aug s ()
tell z = ((),z)
listen :: Aug s a -> Aug s (a,s)
listen (x,z) = ((x,z),z)
pass :: Aug s (a,s->s) -> Aug s a
pass ((x,f),z) = (x, f z)
-- комонадный интерфейс (общий параметр у цепочки параметризованных преобразований)
-- различия с монадным интерфейсом для Param s a минимальны:
-- для Param s начальное значение параметризовано
-- для Aug s начальное значение не параметризовано
(<<=) :: (Aug s a -> b) -> Aug s a -> Aug s b
f <<= (x,z) = (f (x,z), z)
extract :: Aug s a -> a
extract (x,_) = x
ask :: Aug s a -> s
ask (_,z) = zОдин из важнейших типов в информатике вообще: s -> (a,s). Точнее говоря, важным является не сам тип, а его монадный интерфейс.
Монадные модификаторы таких типов (отображения типа a -> s -> (b,s)) называются абстрактными автоматами. Абстрактные автоматы являются низкоуровневой моделью реальных вычислительных устройств.
type State s a = s -> (a, s)
-- функториальный интерфейс является композицией интерфейсов Param и Aug
f <$> t = \s0 -> case t s0 of
(v, s1) -> (f v, s1)
-- аппликативный интерфейс
f <*> t = \s0 -> case t s0 of
(v, s1) -> case f s1 of
(g, s2) -> (g v, s2)
aid = \s0 -> (id, s0)
-- монадный интерфейс
f =<< t = \s0 -> case t s0 of
(v, s1) -> f v s1
pure x = \s0 -> (x, s0)
get :: State s s
get = \s0 -> (s0, s0)
modify :: (s -> s) -> State s ()
modify f = \s0 -> ((), f s0)Преобразователи состояний являются композицей типов Param и Aug. Курсоры – композиция этих же типов в другом порядке. Они обладают полезным комонадным интерфейсом.
type Cursor s a = (s -> a, s)
-- функториальный интерфейс
f <$> (at, cursor) = (f . at, cursor)
-- комонадный интерфейс
f <<= (at, cursor) = (newAt, cursor)
where
newAt c = f (at, c)
extract (at, cursor) = at cursor
seek to (at, cursor) = (at, to)Комонадный интерфейс напоминает функториальный интерфейс к контейнерам, только позволяет выбирать преобразование хранимых данных в зависимости от их положения в контейнере.
Самому преобразованию, в отличие от комонадных преобразований Param, доступна не относительная адресация (относительно положения модифицируемого элемента), а абсолютная.
Обобщённым двойным отрицанием типа a называется тип (a->s)->s. Величины этого типа можно воспринимать как вычисления, подставляющие свой результат в заданное «продолжение».
Этот тип (а точнее, его монадный интерфейс) предоставляет альтернативный преобразователям состояния способ писать «императивный» код. Перед тем, как более просто устроенный тип IO (изоморфный State RealWorld) пришёл в язык Haskell, для задач ввода-вывода использовался именно тип двойных «отрицаний».
Истоки этого типа лежат в классической логике: двойное отрицание к выражению A – это выражение (A ⇒ ⊥) ⇒ ⊥ (символ ⊥ – классическое обозначение для «универсального противоречивого высказывания»).
type C s a = (a -> s) -> s
-- функториальный интерфейс
f <$> c = \next -> c (next . f)
-- монадный интерфейс
f =<< c = \next -> c $ \result -> f result next
pure :: a -> C s a
pure x = \next -> next x
goto :: (a -> s) -> a -> C s b
goto next x = \_ -> next x
callCC :: ((a -> C s b) -> C s a) -> C s a
callCC f = \next -> f (goto next) next@ 2016 arbrk1, all rights reversed