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

Question

Я читаю Программирование Грэма Хаттона в Haskell, и меня смущает поток мыслей, изложенный ниже.

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

Дано:

data Expr = Val Int | Div Expr Expr

safediv :: Int -> Int -> Maybe Int
safediv _ 0 = Nothing
safediv n m = Just (n `div` m)

eval :: Expr -> Maybe Int
eval (Val n) = pure n                               --type: Just(n)?
eval (Div x y) = pure safediv <*> eval x <*> eval y --type: Maybe(Maybe Int)?

Он идет объяснить:

Однако это определение не является корректным типом. В частности, функция safediv имеет тип Int->Int->Maybe Int, тогда как в вышеприведенном контексте требуется функция типа Int->Int->Int.

Замена pure safediv пользовательской функцией намотки тоже не поможет, поскольку эта функция должна иметь тип Maybe(Int->Int->Int), который не предоставляет никаких средств для указания сбоя, когда второй целочисленный аргумент равен нулю. (X)

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

Я не Haskell программист, но из типа eval (Div x y) кажется, что это Maybe(Maybe Int) - который может быть просто сжато , нет? (Что-то вроде flatten в Scala или join в Haskell). Что на самом деле является проблемой здесь?

Независимо от того, x,y Just(s)/Nothing(s) кажется, safediv будет правильно оценивать - единственная проблема здесь - это тип возвращаемого значения, которое можно преобразовать соответственно. Как именно автор go из своего рассуждения к такому выводу это то, что мне трудно понять.

... ограничения аппликативного стиля ограничивают нас применением чистых функций к эффективным аргументам

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

Я понимаю, что аппликативы могут быть использованы для более эффективной цепочки вычислений, когда результаты одного не влияют на другой - но в этом случае я довольно запутан относительно того, как / где произойдет сбой, и если простое исправление типа возврата решит проблему:

eval (Div x y) = join(pure safediv <*> eval x <*> eval y)

А safediv должен быть чистым ? AFAIK это также может быть типа F[Maybe] или F[Either], нет? Что я могу пропустить? Я вижу , куда он идет, но не уверен, что это правильный пример, чтобы попасть туда ИМХО.

Answer 1

Я не Haskell программист, но из типа eval (Div x y) кажется, что это Maybe(Maybe Int) - который может быть просто раздавлен , нет? (Что-то вроде flatten в Scala или join в Haskell). Что на самом деле является проблемой здесь? … Единственная проблема здесь - это тип возвращаемого значения, которое может быть преобразовано соответствующим образом

Этот является ключевым вопросом! «Squashing» - это принципиально монадиальная c операция - фактически сигнатура типа join равна join :: Monad m => m (m a) -> m a. Если вы ограничиваетесь аппликативными методами pure и (<*>), реализовать это невозможно, но это станет проще, если вы позволите себе также использовать (>>=). Конечно, вы можете легко реализовать flattenMaybe :: Maybe (Maybe a)) -> Maybe a без использования монад, но это противоречит цели таких понятий, как Applicative и Monad, которые должны применяться к широкому диапазону типов, а не только к Maybe.

Независимо от того, являются ли x,y Just(s)/Nothing(s), кажется, safediv правильно оценит - единственная проблема здесь - это тип возвращаемого значения, который может быть преобразован соответствующим образом. Как именно автор go из своих рассуждений приходит к такому заключению, это то, что мне трудно понять.

... ограничения аппликативного стиля ограничивают нас применением чистых функций к эффективным аргументам

Кроме того, почему параграф, отмеченный (X) выше, делает это утверждение, когда проблема только Похоже, что это или возвращаемое смещение типа.

Идея в следующем. Допустим, у вас есть две функции и два значения:

nonEffectful :: a -> b -> c
effectful    :: a -> b -> m c

effectfulA :: m a
effectfulB :: m b

Теперь, если вы хотите применить функцию nonEffectful к двум эффективным аргументам, m должно быть только Applicative: это легко сделать nonEffectful <$> effectfulA <*> effectfulB :: m c. Но если вы попробуете это с функцией effectful, вы столкнетесь с проблемой: вы получите тип возврата m (m c) вместо m c. Чтобы «раздавить» m (m c) в m c, вам нужен экземпляр Monad. Таким образом, аппликативные функции могут применять только чистые (неэффективные) функции к эффективным аргументам, но монады позволяют применять эффективные функции к эффективным аргументам. Это то, что Хаттон пытался сделать, но с определенной c функцией safeDiv :: Int -> Int -> Maybe Int.

(Одна вещь, которую я не упомянул в приведенном выше обсуждении, это интуиция: почему на интуитивном, а не на формальном уровне требуются монады для конкретных c вычислений? Как вы уже заметили, ответ связан с зависимостями. Для nonEffectful <$> effectfulA <*> effectfulB два эффективных значения не влияют друг на друга. Однако с effectful <$> effectfulA <*> effectfulB внезапно возникает зависимость: функция effectful должна зависеть от результатов эффективных вычислений, переданных ей. Monad можно рассматривать как представление идеи эффективных вычислений, которые могут зависеть друг от друга тогда как Applicative представляет идею эффективных вычислений, которые не могут зависеть друг от друга (хотя чистая функция может зависеть от них). Аналогично, для оценки вложенных вычислений m (m a) сначала необходимо оценить внешние вычисления, а затем оцените результирующее внутреннее эффективное вычисление. Снова у нас есть эффект ctful вычисление, которое зависит от другого эффективного вычисления, поэтому для этого требуется Monad.)