Русский
Русский
English
Статистика
Реклама

Functor

Повесть о стрелке и запятой

18.10.2020 20:21:07 | Автор: admin
В этой статье мы:

  • Познакомимся с сопряженными функторами
  • Узнаем, как отвечать на вопрос что такое каррирование
  • Притворимся, что у нас есть состояние (если есть только функции)
  • И вдогонку поиграемся с примитивной оптикой (линзами)


И все это с помощью нескольких определений теории категорий и двух простейших конструкций: стрелки и запятой.




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

Функции и кортежи



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

Что такое функция? Это отображение одного множества на другое. Это кусок кода, принимающий аргумент s и возвращающий результат a: s -> a.



Что такое кортеж? Это самое элементарное произведение двух любых типов s и a: (s, a).



Мы привыкли смотреть на эти две конструкции в инфиксной форме. Что если мы немного изменим угол обзора и посмотрим префиксно, то есть выставим операнды после оператора?




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




И теперь они не только являются ковариантными функторами, но еще и формируют такое интересное отношение как сопряжение!



Но обо всем по порядку.

Категории, функторы, сопряжения



Категория это набор объектов и стрелок между ними:


What is a Category? Definition and Examples Math3ma

Функторы это отображения между категориями:


What is a Functor? Definition and Examples, Part 1 Math3ma

А сопряжение это особое отношение между функторами. То есть, если мы можем построить две такие коммутативные диаграммы, и равенства выполняются, мы говорим что F и G сопряженные функторы (F G):


What is an Adjunction? Part 2 (Definition) Math3ma

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

Сопряжение запятой и стрелки



Примерно так выглядит определение функтора в языках с параметрическим полиморфизмом:



Начнем с того, что функция и кортеж это функторы:



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



А в случае со стрелкой, определение отображения совпадает с композицией функций!

Пожалуй, определения сопряженного функтора в коде выглядит достаточно запутанно:



Поэтому вместо операции сопряжения слева и сопряжения справа, мы определим кое-что попроще единицу и коединицу. Помните те две коммутативные диаграммы? Операция соответствует коединице, а единице:


What is an Adjunction? Part 2 (Definition) Math3ma

Начнем с коединицы:

 :: f (g a) -> a-- Вместо f и g подставляем запятую и стрелку: :: (((,) s) ((->) s a)) -> a-- Раскрываем скобки для запятой - из префиксной нотации в инфиксную: :: (s, ((->) s a)) -> a-- Раскрываем скобки для стрелки - из префиксной нотации в инфиксную: :: (s, s -> a) -> a


Что у нас тут получилось? Коединица для запятой и стрелки, которая принимает какой-то аргумент s, функцию из s в a. Хм, выглядит как применение функции:

 :: (s, s -> a) -> a (x, f) = f x


Отлично, 90% работы проделано осталось еще 90%. Теперь возьмемся за единицу:

 :: a -> g (f a)-- Вместо f и g подставляем запятую и стрелку: :: a -> ((->) s ((,) s a))-- Раскрываем скобки для стрелки - из префиксной нотации в инфиксную: :: a -> s -> ((,) s a)-- Раскрываем скобки для запятой - из префиксной нотации в инфиксную: :: a -> s -> (s, a)


Итак, единица принимает s, a и собирает их в кортеж в обратном порядке, проще некуда:

 :: a -> s -> (s, a) x s = (s, x)


А теперь вернемся к тем самым операциям, которые выглядели так страшно еще несколько абзацев назад:



Попробуем реализовать сопряжение слева и сопряжение справа:



Уффф, что-то легче не стало. Порой, в попытке что-то понять, у нас нет другого выбора кроме как посмотреть на это очень внимательно. Давайте прямо сейчас это и сделаем.

Сопряжение слева: принимает функцию, которая принимает кортеж (s, a) -> b и результатом становится функция, которая поочередно принимает по одному аргументу сначала a, потом s:



Сопряжение слева наоборот: принимает функцию, которая возвращает функцию (a -> (s -> b)) и результатом становится выражение, которое принимает кортеж.



Вам это ничего не напоминает? Да это же каррирование!

curry :: ((a, s) -> b) -> a -> s -> buncurry :: (a -> s -> b) -> (a, s) -> b

(Единственное отличие в том, что аргументы a и s идут в обратном порядке)

Если вдруг вам на собеседовании зададут вопрос что такое каррирование, можете смело отвечать: Это всего лишь сопряжение слева функтора кортежа по функтору функции, в чем проблема?

Комбинаторика функторов



Идея: давайте попробуем составить простую композицию функторов стрелки и запятой, а потом посмотрим, что получится. Простая композиция это просто оборачивание одного функтора в другой, ведь они полиморфны по своему аргументу. Сделать мы это можем двумя способами:



На место f и g подставляем запятую и стрелку (с фиксированными аргументами) соответственно:



Выглядит как-то знакомо, правда? Еще как! В одной комбинации мы получаем комонаду Store, а в другой монаду State.




И они также образуют сопряжение!



Состояние и хранилище



Что мы себе представляем в первую очередь, когда создаем программы, которые зависят не только от своего аргумента, но и от какого-нибудь состояния? Наверное, то, что мы кладем/извлекаем некоторое значение в коробочке. Или, в случае конечного автомата, мы концентрируемся на переходах:



Что же, для переходов у нас есть стрелка, а для коробочки кортеж:

type State s a = s -> (s, a)-- Изменить хранимое состояние с помощью функцииmodify :: (s -> s) -> State s ()modify f s = (f s, ())-- Получить хранимое состояниеget :: State s sget s = (s, s)-- Заменить хранимое состояние другимput :: s -> State s ()put new _ = (new, ())


Хранилище это что-то совершенно другое. Мы храним некоторый источник s и инструкцию о том, как из этого s получить а:

type Store s a = (s, s -> a)pos :: Store s a -> spos (s, _) = speek :: s -> Store s a -> apeek s (_, f) = f sretrofit :: (s -> s) -> Store s a -> Store s aretrofit g (s, f) = (g s, f)


Где же это может использоваться?

Фокусируемся с линзами



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



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



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

view :: Lens s t -> s -> tview lens = pos . lensset :: Lens s t -> t -> s -> sset lens new = peek new . lensover :: Lens s t -> (t -> t) -> s -> sover lens f = extract . retrofit f . lens


Изменяем состояние с линзами



Давайте рассмотрим эту магию в действии. Жил был человек:

data Person = Person Name Address (Maybe Job)


У нас есть линзы, которые могут фокусироваться на его работе и адресе проживания:

job :: Lens Person (Maybe Job)address :: Lens Person Address


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

hired :: State (Maybe Job) Cityrelocate :: City -> State Address ()


Итак, у нас есть выражение hired, которое оперирует состоянием текущей работы (Maybe Job). Также есть выражение, которое принимает в качестве аргумента город и в зависимости от этого меняет свое состояние Address. Оба выражения имеют эффект состояния, но мы не можем их использовать вместе, потому что тип состояний разный.

Но у нас есть волшебная функция zoom, которая позволяет с помощью линзы из большего состояния в меньшее подниматься до уровня нужного нам состояния (очень похоже на метод поднятия эффектов lift в монадных трансформерах).

zoom :: Lens bg ls -> State ls a -> State bg a


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

zoom job hired :: State Person Cityzoom address (relocate _) :: State Person ()


И связываем эти выражения в монадный конвеер! Теперь мы имеем доступ к состоянию Person во всем связанном выражении:

zoom job hired >>= zoom address . relocate


Исходники с определениями можно найти здесь.
Подробнее..

Пытаясь композировать некомпозируемое монады

04.01.2021 22:21:38 | Автор: admin

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

Рекомендуется прочитать первую и вторую части этой серии, если вы еще этого не сделали.

Когда мы хотим слить два эффекта в один, то есть сцепить их в трансформер, у нас есть два варианта: вложить левый в правый, либо правый в левый. Эти два варианты определены со схемами TU и UT:

newtype TU t u a = TU (t :. u := a)newtype UT t u a = UT (u :. t := a)

Как нам уже известно из предыдущих частей этого цикла, для вычислений с неизменяемым окружением (Reader) достаточно прямой композиции функторов, а для эффектов обработки ошибок (Maybe и Either) подходит схема с обратной композицией UT.

type instance Schema (Reader e) = TU ((->) e)type instance Schema (Either e) = UT (Either e)type instance Schema Maybe = UT Maybe

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

(<$$>) :: (Functor t, Functor u) => (a -> b) -> t :. u := a -> t :. u := b(<$$>) = (<$>) . (<$>)(<**>) :: (Applicative t, Applicative u) => t :. u := (a -> b) -> t :. u := a -> t :. u := bf <**> x = (<*>) <$> f <*> xinstance (Functor t, Functor u) => Functor (TU t u) where    fmap f (TU x) = TU $ f <$$> xinstance (Applicative t, Applicative u) => Applicative (TU t u) where    pure = TU . pure . pure    TU f <*> TU x = TU $ f <**> xinstance (Functor t, Functor u) => Functor (UT t u) where    fmap f (UT x) = UT $ f <$$> xinstance (Applicative t, Applicative u) => Applicative (UT t u) where    pure = UT . pure . pure    UT f <*> UT x = UT $ f <**> x

Проблемы возникают, если мы попробуем описать монады. Непонятно, как найти обобщенный способ, учитывая, что оба эффекта нам неизвестны:

instance (Monad t, Monad u) => Monad (TU t u) where  x >>= f = ???instance (Monad t, Monad u) => Monad (UT t u) where  x >>= f = ???

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

instance Monad u => Monad (TU ((->) e) u) where    TU x >>= f = TU $ \e -> x e >>= ($ e) . run . finstance Monad u => Monad (UT (Either e) u) where    UT x >>= f = UT $ x >>= \case        Left e -> pure $ Left e        Right r -> run $ f rinstance Monad u => Monad (UT Maybe u) where    UT x >>= f = UT $ x >>= \case        Nothing -> pure Nothing        Just r -> run $ f r

В случае обработки ошибок (Maybe и Either), мы можем увидеть похожее поведение: если инвариант содержит параметр a, тогда цепочка вычислений продолжается. Это невероятно похоже на Traversable! Вот так он выглядит:

class (Functor t, Foldable t) => Traversable t where    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)instance Traversable Maybe where    traverse _ Nothing = pure Nothing    traverse f (Just x) = Just <$> f xinstance Traversable (Either a) where    traverse _ (Left x) = pure (Left x)    traverse f (Right y) = Right <$> f y

Давайте попробуем его использовать:

instance (Traversable t, Monad t, Monad u) => Monad (UT t u) where    UT x >>= f = UT $ x >>= \i -> join <$> traverse (run . f) i

Работает! То есть, мы можем применять связывание для трансформера с известным нам Traversable эффектом.

А что нам делать с TU, для которого подходит эффект неизменяемого окружения - Reader? Я правда не знаю. Но мы можем кое-что попробовать - возьмём класс антипод Traversable - Distributive. И какое счастье, для него может быть определен Reader (точнее, его внутренняя часть - (->) e)!

class Functor g => Distributive g where    collect :: Functor f => (a -> g b) -> f a -> g (f b)instance Distributive ((->) e) where    collect f q e = flip f e <$> q

Но почему именно эти два класса функторов и почему они антиподы по отношению друг к другу? Понять это помогут модификации их методов, где вместо функций a -> t b мы подставляем функцию, которая ничего не меняет - id:

sequence :: (Traversable t, Applicative u) => t (u a) -> u (t a)sequence = traverse iddistribute :: (Distributive t, Functor u) => u (t a) -> t (u a)distribute = collect id

Вот оно! Мы можем увидеть, что эти методы позволяют нам менять порядок эффектов. Раз уж сработал Traversable для обратной композиции, может Distributive подойдет для прямой?

instance (Monad t, Distributive t, Monad u) => Monad (TU t u) where    TU x >>= f = TU $ x >>= \i -> join <$> collect (run . f) i

Тоже работает! Значит у нас уже есть определенный алгоритм, как определять монады для таких трансформеров:

  • Обратная схема UT - полагайся на Traversable.

  • Прямая схема TU - полагайся на Distributive.

Но у нас есть также схема посложнее, которая используется в монаде State и комонаде Store:

newtype TUT t t' u a = TUT (t :. u :. t' := a)newtype State s a = State ((->) s :. (,) s := a)newtype Store s a = Store ((,) s :. (->) s := a)type instance Schema (State s) = TUT ((->) s) ((,) s)type instance Schema (Store s) = TUT ((,) s) ((->) s)

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

instance (Functor t, Functor t', Functor u) => Functor (TUT t t' u) where    fmap f (TUT x) = TUT $ f <$$$> x

Так, стрелка ( (->) s) является Distributive, а запятая ((,) s) - Traversable... Но между этими двумя эффектами также существует связь посильнее, которая называется сопряжением (подробнее можно почитать здесь):

class Functor t => Adjunction t u where    leftAdjunct  :: (t a -> b) -> a -> u b    rightAdjunct :: (a -> u b) -> t a -> b    unit :: a -> u :. t := a    unit = leftAdjunct id    counit :: t :. u := a -> a    counit = rightAdjunct idinstance Adjunction ((,) s) ((->) s) where    leftAdjunct :: ((s, a) -> b) -> a -> (s -> b)     leftAdjunct f a s = f (s, a)    rightAdjunct :: (a -> s -> b) -> (s, a) -> b    rightAdjunct f (s, a) = f a s    unit :: a -> s -> (s, a)    unit x = \s -> (s, x)    counit :: (s, (s -> a)) -> a    counit (s, f) = f s

Попробуем сначала разобраться с эффектом состояния. Погружение в эффект State полностью идентичен методу unit, а сопряжение справа используется, чтобы связать два эффекта в монадной цепочке:

instance Monad (State s) where    State x >>= f = State $ rightAdjunct (run . f) <$> x    -- Или так: State x >>= f = State $ counit <$> ((run . f) <$$> x)    return = State . unit

А как быть в случае с трансформером? Тут у нас меж двух функторов ((->) s) и ((,) s) есть произвольный эффект, который надо учитывать. Для погружения в трансформер нам понадобится сопряжение слева, а для связывания - сопряжение справа:

instance (Adjunction t' t, Monad u) => Monad (TUT t t' u) where    x >>= f = TUT $ (>>= rightAdjunct (run . f)) <$> run x    return = TUT . (leftAdjunct pure)

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

instance (Adjunction t' t, Comonad u) => Comonad (TUT t' t := u) where    extend f x = TUT $ (=>> leftAdjunct (f . TUT)) <$> run x    extract = rightAdjunct extract . run

А что, если нам нужно не только погружать значение в трансформер, но еще и поднимать произвольный эффект до уровня трансформера? И тут нам понадобятся сопряжения! Причем, для монадных и комонадных трансформеров результаты невероятно симметричны...

instance (Adjunction t' t, Distributive t) => MonadTrans (TUT t t') where    lift = TUT . collect (leftAdjunct id)instance (Adjunction t' t, Applicative t, forall u . Traversable u) => ComonadTrans (TUT t' t) where    lower = rightAdjunct (traverse id) . run

Из этого всего, мы можем сделать выводы:

  • Если эффект имеет экземпляр Traversable - подходит обратная схема UT.

  • Если эффект имеет экземпляр Distributive - подходит прямая схема TU.

  • Если компоненты эффекта образуют сопряжение (Adjunction) - подходит схема TUT.

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

Исходники с определениями можно найтиздесь. Примеры применения описанной системы эффектов можно посмотреть тут.

Подробнее..

Перевозим волка, козу и капусту через реку с эффектами на Haskell

02.08.2020 16:06:23 | Автор: admin
Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту.




В этой статье мы попытаемся найти обобщенное решение для такого типа головоломок и для этого будем использовать алгебраические эффекты.



Начнем с самого простого маршрута перемещений. Так как мы не знаем заранее, через какое гарантированное количество шагов мы получим решение, можно построить бесконечный маршрут, все равно мы будем вычислять его лениво:

data Direction = Back | Forwardroute :: [Direction]route = iterate alter Forwardalter :: Direction -> Directionalter Back = Forwardalter Forward = Back


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

data Character = Wolf | Goat | Cabbage deriving Eqclass Survivable a wheresurvive :: a -> a -> Orderinginstance Survivable Character wheresurvive Wolf Goat = GTsurvive Goat Wolf = LTsurvive Goat Cabbage = GTsurvive Cabbage Goat = LTsurvive _ _ = EQ


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

  • Чтобы найти решение, при котором все персонажи будут перевезены на противоположный берег, надо перебрать много вариантов перестановок. Для этого мы будем использовать эффект множественности, которого можно добиться с помощью обычного списка.
  • Еще нам нужно запоминать местоположение персонажа, чтобы проверять условия совместимости с другими персонажами (волк ест козу, коза ест капусту) и кого можно посадить на лодку. Мы можем хранить состав двух берегов type River a = ([a],[a]) c помощью эффекта состояния State (River a).
  • Лодка может взять кого-нибудь на борт, а может и не брать тут нам пригодится эффект частичности с Maybe.


В коде я буду использовать свою экспериментальную библиотеку joint (на Хабре есть две статьи, объясняющие ее суть первая и вторая), но при желании решение можно перенести на transformers или mtl.

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

  • В аппликативной/монадной цепочке вычислений для Maybe, если мы где-то получили Nothing, то и результат всего вычислений будет Nothing. Мы оставим его отдельно, так как не хотим, чтобы при отправлении пустой лодки (без персонажа, крестьянина мы не учитываем) мы потеряли весь прогресс в нахождении решения.
  • Каждый последующий выбор хода (эффект множественности) должен опираться на состав текущего берега (эффект состояния), так как мы не можем взять персонажа в лодку, если она находится на другом берегу. Следовательно, нам нужно эти эффекты сцепить в трансформер: State (River a) :> [].


Один ход в головоломке можно описать как последовательность действий:

  1. Получить состав персонажей на текущем берегу
  2. Выбрать следующего персонажа для транспортировки
  3. Переместить персонажа на противоположный берег


step direction = bank >>= next >>= transport


Давайте пройдемся по каждому шагу подробнее.

В зависимости от направления перемещения лодки, применяем линзу для источника отправления к состоянию всей реки и получаем состав текущего берега:

bank :: (Functor t, Stateful (River a) t) => t [a]bank = view (source direction) <$> current


Выбор следующего персонажа происходит так: получая набор персонажей с берега (предыдущее выражение bank), мы формируем пространство выбора, добавляя к этому самому пространству пустую лодку:

\xs -> Nothing : (Just <$> xs) 


Для каждого кандидата (пустая лодка (Nothing) тоже кандидат) проверяем чтобы на оставшемся берегу не оставалось персонажей, которые были бы не прочь полакомиться друг другом:

valid :: Maybe a -> Boolvalid Nothing = and $ coexist <$> xs <*> xsvalid (Just x) = and $ coexist <$> delete x xs <*> delete x xscoexist :: Survivable a => a -> a -> Boolcoexist x y = survive x y == EQ


И когда мы отфильтровали пространство выбора персонажей, поднимаем эффект множественности и возвращаем каждый элемент из этого пространства выбора:

next :: (Survivable a, Iterable t) => [a] -> t (Maybe a)next xs = lift . filter valid $ Nothing : (Just <$> xs)


Остался последний шаг фактическая транспортировка c помощью линз: удаляем персонажа с берега отправки и добавляем к берегу назначения:

leave, land :: River a -> River aleave = source direction %~ delete xland = target direction %~ (x :)


Если в лодке был персонаж изменяем состояние реки, иначе ход был холостым:

transport :: (Eq a, Applicative t, Stateful (River a) t) => Maybe a -> t (Maybe a)transport (Just x) = modify @(River a) (leave . land) $> Just x wheretransport Nothing = pure Nothing


Было бы неплохо посмотреть на работу программы в действии. Для нахождения решения нам нужно как минимум совершить семь шагов по маршруту:

start :: River Characterstart = ([Goat, Wolf, Cabbage], [])solutions = run (traverse step $ take 7 route) start


И у нас есть два решения:



Полные исходник можно посмотреть здесь.
Подробнее..

Заберите свои скобки

09.06.2021 10:16:43 | Автор: admin

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

В большинстве современных языков программирования скобки используются в качестве оператора применения функции к ее аргументам:

q (x, y z)

Но вHaskellоператор применения функции - это обычный пробел:

q :: a -> b -> c -> dx :: ay :: bz :: yq x y z

Подождите-ка, мы применяем функциюfк аргументам, а пробелов намного больше! Значит ли это, что у нас тут несколько применений функции к аргументам? Да:

(((q x) y) z)

Мы получаем несколько применений функции в каррированной форме:

q x :: b -> c -> dq x y :: c -> dq x y z :: d

Значит ли это, что мы можем отказаться от скобок? Нет, потому что в качестве аргументов нам могут попадаться применения функций, нам может быть просто лень придумывать новое имя для выражения, которое будет лишь промежуточным шагом:

q:: a -> b -> c -> dp:: b -> cq x y (p y)

И вот тут без скобочек нам не обойтись, потому что иначе проверка типов будет считать, что мы подаем на вход функцииfдва разных аргумента:

q :: a -> b -> (b -> c) -> b -> ???q x y p y

К счастью, у нас уже есть инфиксный оператор в базовой библиотеке, который поможет нам избавиться от ненужных скобок:

q:: a -> b -> c -> dp:: b -> cq x y $ p y

Этот оператор ($) обычно называют применением - мы всего лишь явно отделяем функцию от аргумента, который нужен ей для получения результата.

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

($) :: a -> (a -> b) -> bo :: d -> eo (q x y $ p y) === o $ q x y $ p y

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

"What is a Category? Definition and Examples" (c) Math3ma

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

f :: a -> bg :: b -> cg . f :: a -> c(.) :: (b -> c) -> (a -> b) -> (a -> c)g (f x) === g . f

Зачастую вопрос о том, использовать ли композицию или применение - стилистический, так как эти два представления приводят к одному и тому же результату:

g . f === g $ f x

Если у нас в выражении есть где-то свободная переменная, мы можем применить ее с помощью одного оператора применения, а дальше использовать композицию (я в большинстве случаев именно так и делаю). Да и код читается намного лучше:

j $ h $ f $ g $ x === j . h . f . g $ x

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

f :: a -> b -> cg :: a -> b -> c -> dh :: c -> d -> eh (f x y) (g x y z)

Можно убрать лишь скобки справа:

h (f x y) (g x y z) === h (f x y) $ g x y z

Как убрать скобки слева? Чтобы понять, как подступиться к этой проблеме, давайте разберем композицию (.) и применение ($). Оба эти оператора - правоассоциативные. Ассоциативность - это про скобки. Ассоциативность справа - значит скобки группируются справа.

f . g . h === f $ g $ h x === f (g (h x))

Так как в Haskell функции уже в каррированной форме, мы не обязаны подавать все аргументы сразу - мы можем подавать их по одному.

f :: a -> b -> c -> df x :: b -> c -> df x y :: c -> df x y z :: d

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

(???) :: (a -> b -> c -> ...) -> a -> b -> c -> ...((??? x) y) z) ...

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

maybe :: b -> (a -> b) -> Maybe a -> b

Давайте выберем для нашего нового оператора какой-нибудь ASCII-символ, который еще вроде никак не используется в базовой библиотеке.

(#) :: (a -> b -> c -> ...) -> a -> b -> c -> ...f # x y z ... = ???

Кроме ассоциативности, для оператора нужно выбрать старшинство - это номер от 0 до 9, который определяет приоритет операторов. Чем выше номер, тем ниже приоритет. Например:

infixr 9 .infixr 0 $

Именно поэтому мы группируем скобки вокруг$, а не.:

h . g . f $ x === (h . (g . f)) $ (x)

В общем, для нашего нового оператора мы вольны выбрать любое число между 0 и 9. Давайте выберем что-нибудь среднее - 5.

infixl 5 #

Но как нам его написать? На самом деле, это тоже оператор применения, только сфокусированный на функции, а не на аргументах:

f # x = f x

Эмм... и как это работает? Рассмотрим лучше на каком-нибудь примере - пусть это будет тот же обработчик опциональной ошибки. Так как функции уже находятся в каррированной форме, мы можем скармливать аргументы один за другим:

maybe :: b -> (a -> b) -> Maybe a -> bmaybe x :: (a -> b) -> Maybe a -> bmaybe x f :: Maybe a -> bmaybe x f ma :: b

Каррирование... отлично, значит, мы можем группировать скобки слева!

maybe # x # f # ma === ((maybe # x) # f) # mamaybe # "undefined" # show . even # Just 1 === "False"maybe # "undefined" # show . even # Just 2 === "True"maybe # "undefined" # show . even # Nothing === "undefined"

Если применяемые аргументы достаточно большие и нет особой надобности в том, чтобы придумывать им имена, мы можем выстроить их в такой блок с отступом:

string_or_int :: Either String Inteither :: (a -> c) -> (b -> c) -> Either a b -> ceither  # print . ("String: " <>)  # print . ("Int: " <>) . show # string_or_int

Я пока что нигде еще не видел такого оператора, но мне бы он сильно понадобился там, где не справляются$и.. Напишите в комментариях, если подобное уже где-то существует, но по какой-то причине отсутсвует вbase.

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru