Понимание функции связывания в Haskell

Question

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

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

Answer 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

В случае . сначала выполняется «1008 *», изатем 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)?

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

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

Answer 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 может рассматриваться как недетерминированное вычисление.Итак, мы определяем что-то вроде:

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

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

Answer 3

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

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

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

Answer 4

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

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