Понимание функции bind в Haskell

Я знаком с монадами в теории категорий (на самом деле это очень простая концепция), но функция >>= в Haskell полностью меня озадачивает. Итак, применяя привязку к значению M a, а функция a -> M u совпадает с первым применением монады к этой функции, затем оценивая ее по указанному значению и умножая результат: a >>= f совпадает с join $ (fmap f) $ a. Но как это естественное описание вычислений? Есть ли какой-нибудь полезный способ взглянуть на него, что поможет мне понять это?

Есть ли какая-нибудь хорошая статья где-то, которая не ориентирована на кого-то нового из джунглей С++?

Ответ 1

Рассмотрим оператор композиции монадической функции <=<. Это аналогично ., за исключением того, что оно работает над монадическими функциями. Его можно определить просто в терминах >>=, поэтому изучение одного из нас будет информировать нас о другом.

(<=<) :: (a -> m b) -> (b -> m c) -> a -> m c
(f <=< g) x =  g x >>= f

(.) :: (a -> b) -> (b -> c) -> a -> c
(f . g) x = g x |> f
  where z |> h = h z

В случае . сначала выполняется "t25 > ", а затем f выполняется на выходе g. В случае <=<, g и его эффекты сначала выполняются, а затем f и его эффекты выполняются. Это немного неправильно, чтобы сказать, что на самом деле происходит "до" другого, так как не все монады работают таким образом.

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

Но почти во всех нетривиальных случаях f <=< g означает, что эффекты (а также результат) монадической функции g будут впоследствии влиять на поведение монадической функции f.

Чтобы задать вопросы о v >>= f = join (fmap f v)

Рассмотрим f :: a -> m b и v :: m a. Что значит fmap f v? Ну fmap :: (c -> d) -> m c -> m d, и в этом случае c = a и d = m b, поэтому fmap f :: m a -> m (m b). Теперь, конечно, мы можем применить v :: m a к этой функции, в результате получим m (m b). но что именно означает этот результат типа m (m b)?

Внутренний m представляет контекст из f. Внешний m представляет контекст, происходящий из v (n.b. fmap не должен нарушать этот исходный контекст).

И затем вы join, что m (m b), разбивая эти два контекста вместе на m a. Это основа определения Monad: вы должны предоставить способ разбить контексты вместе. Вы можете проверить детали реализации различных экземпляров Monad, чтобы попытаться понять, как они "разбивают" контексты вместе. Вывод здесь, однако, заключается в том, что "внутренний контекст" ненаблюдаем, пока вы не объедините его с "внешним контекстом". Если вы используете v >>= f, то нет фактического понятия функции f, получающей чистое значение a и создающего простой монадический результат m b. Вместо этого мы понимаем, что f действует в исходном контексте v.

Ответ 2

Хм. Я думаю, что хороший способ подумать о том, что >>= позволяет вам составлять вычисления; сами вычисления выполнены в виде a -> m b. Итак, m b просто представляет результат вычисления.

Итак, вычисление просто берет некоторое значение и дает некоторый результат. Хорошим примером здесь является тип списка: a -> [b] представляет собой недетерминированное вычисление. Он принимает один вход, но может давать несколько результатов. Сам по себе a -> [b] как вычисление имеет смысл. Но как бы вы их объединили? Естественным ответом является то, что вы будете выполнять каждое последовательное "вычисление" во всех предыдущих результатах. И это именно то, что >>= делает для списков.

Одна вещь, которая действительно помогла мне понять практическую ценность этого, - это думать о DFA и NFA. Вы можете представить себе тривиальное письмо DFA в Haskell примерно так:

data State = S1 | S2 | S3 | S4 | Q
data Input = A | B
transition :: State -> Input -> State
transition S1 A = S2
transition S1 B = S3
-- and so on...

Тогда мы могли бы просто сбрасывать ввод:

 foldl transition S1 [A, A, B, B]

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

transition S1 A = [S1, S2]
transition S1 B = []

Но теперь нам нужно сделать какую-то странную гимнастику, чтобы использовать foldl! К счастью, мы можем просто foldM. Итак, здесь "вычисление", смоделированное монадой, является недетерминированной функцией перехода.

Ответ 3

Возможно, =<< легче понять с точки зрения вычислений (это просто flip (>>=)). Он набирает (=<<) :: (Monad m) => (a -> m b) -> m a -> m b и соответствует типу приложения функции, cf ($) :: (a -> b) -> a -> b. Таким образом, >>= - это просто перевернутое функциональное приложение на монадическом уровне.

Кроме того, (>>=) используется в desugaring do нотации, а do синтаксически очень соответствует императивному коду (в подходящей монаде).

Ответ 4

Вот приблизительное представление о том, как оно работает как модель вычисления: конструктор типа M с экземпляром Monad представляет собой структуру параметрических данных, а непараметрические части этой структуры могут содержать другую информацию, return и join соответствуют некоторому моноиду для тех частей структуры. Функция a -> M b вводит информацию в эту структуру на основе ввода типа a. Поэтому, поднимая функцию a -> M b до M a -> M b, мы используем параметрическую информацию M для создания некоторой непараметрической информации, а затем комбинируем ее с информацией, уже имеющейся в значении типа M a.

Асимметричный характер типа a -> M b дает неотъемлемое направление потока непараметрической информации, а требование ассоциативности означает, что общий порядок - это единственное, что имеет значение.

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