Вадлер, "Монады для функционального программирования", раздел 2.8

Question

Редактировать II: Ах, ладно: я не понимал, как a и b были связаны в определении eval ! Теперь я делаю. Если кому-то интересно, это схема отслеживания a и b . Я довольно большой поклонник диаграмм. Рисование стрелок действительно улучшило мой Haskell, клянусь.

Диаграмма электронного звонка (PDF)

Иногда я чувствую себя действительно плотно.

---

В разделе 2.8 из " Монад Уодлера для функционального программирования " он вводит состояние в простую функцию оценки. Исходная (не монадическая) функция отслеживает состояние, используя последовательность выражений let, и за ней легко следить:

data Term = Con Int | Div Term Term
 deriving (Eq, Show)

type M a = State -> (a, State)
type State = Int

eval' :: Term -> M Int
eval' (Con a) x   = (a, x)
eval' (Div t u) x = let (a, y) = eval' t x in
                    let (b, z) = eval' u y in
                    (a `div` b, z + 1)

Определения unit и bind для монадического вычислителя также просты:

unit :: a -> M a
unit a = \x -> (a, x)

(>>=) :: M a -> (a -> M b) -> M b
m >>= k = \x -> let (a, y) = m x in
                let (b, z) = k a y in
                 (b, z)

Здесь (>> =) принимает монадическое значение m :: M a , функция k :: a -> M b и выводит монадическое значение M b . Значение m зависит от значения, подставляемого для x в лямбда-выражении.

Wadler затем вводит функцию tick :

tick :: M ()
tick = \x -> ((), x + 1)

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

(1) Как реализован тик . Например, следующее является допустимым вызовом функции:

(tick >>= \() -> unit (div 4 2)) 0
 ~> (2, 1)

Однако я не могу правильно оценить это вручную (что указывает на то, что я что-то неправильно понимаю). В частности: (a) Результат вычисления tick в 0 равен ((), 0), так как лямбда-выражение принимает ()? (b) Если a является первым элементом пары, возвращенной путем вызова tick в 0, как оценивается единица ?

(2) Как объединить отметку и единицу для отслеживания количества выполненных операторов деления. Хотя немонадный анализатор не является проблематичным, использование bind меня здесь смущает.

Редактировать: Спасибо всем. Я думаю, что мое недоразумение было роль лямбда-выражения, '() -> unit (div 4 2)'. Если я правильно понял,

(tick >>= (\() -> unit (div m n)) x

расширяется до

(\x -> let (a, y) = tick x in
       let (b, z) = (\() -> unit (div m n) a y) in
       (b, z)) x

Когда «a» применяется к «() -> единица (div m n) a y», «практический результат» не выдается. Этого же эффекта можно добиться, связав переменную любой с помощью лямбда-оператора и подставив для него значение. В этом случае универсальность bind заключается в том, что любое значение M a может быть передано ему. Как отмечено, значение M a представляет вычисление, например, 'eval.' Следовательно:

eval (Con a) = unit a

eval (Div t u) = eval t >>= (\a ->
                  eval u >>= (\b ->
                   tick >>= (\c -> unit (a `div` b))))

Если я правильно понимаю, вместо eval t вместо m подставляется выражение

.

'(\a -> eval u >>= (\b -> tick >>= (\c -> unit (a `div` b))))'

заменяет k . Результат оценки 'eval t' связан с (a, y), а результат оценки k связан с (b, z). У меня есть способы пойти, но это несколько проясняет. Благодаря.

Answer 1

Вы можете оценить выражение вручную следующим образом:

(tick >>= \() -> unit (div 4 2)) 0

Если вы вставите tick и \() -> unit (div 4 2) в определение >>=, это станет:

(\x -> let (a, y) = tick x in
       let (b, z) = (\() -> unit (div 4 2)) a y in
       (b, z)) 0

Если вы теперь примените функцию, подставив 0 для x, вы получите:

let (a, y) = tick 0 in
let (b, z) = (\() -> unit (div 4 2)) a y in
(b, z)

Теперь давайте применим тик к 0:

let (a, y) = ((), 0 + 1) in
let (b, z) = (\() -> unit (div 4 2)) a y in
(b, z)

То есть a становится (), а y становится 0+1, что составляет 1. Итак, у нас есть

let (b, z) = (\() -> unit (div 4 2)) () 1 in
(b, z)

Если мы применим функцию к (), мы получим

let (b,z) = unit (div 4 2) 1 in
(b,z)

Если мы применим единицу, мы получим

 let (b,z) = (div 4 2, 1) in
 (b,z)

div 4 2 равно 2, поэтому результат равен (2,1).

Answer 2

1a)

Результат вычисления тика в 0: ((), 1) - посмотрите на код еще раз, он увеличивает входное значение на единицу.

Лямбда-выражениеaccepts (), потому что это правая часть операции связывания, то есть ожидается, что ее тип будет (() -> M b).Таким образом, он принимает () в качестве первого параметра, а затем использует «единицу» в качестве элемента M b.

1b)

Я не совсем уверен, о чем вы здесь спрашиваете.Оператор связывания определен для передачи результата и состояния из первой операции (то есть () и 1 соответственно) во вторую операцию, поэтому в конечном итоге блок передается 1 в качестве текущего состояния (результат, (), был поглощенлямбда-выражение).Текущее состояние сохраняется как есть функцией единицы измерения, и результат является результатом 4 div 2, то есть 2.

2)

Предположительно, вам понадобится некоторая функциятип:

divCounted :: Int -> Int -> M Int

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

Answer 3

1a) Результатом вычисления тика в 0 является ((), 1), так как лямбда-выражение принимает ()?

Ключ к монаде состояния состоит в том, что bind заботится о втором компоненте пары, состоянии.Лямбда-выражение должно обрабатывать только (), первый компонент пары, возвращаемое значение.

В общем, ключ к монаде M заключается в том, что он абстрагирует весь процесс создания потоковсостояние прочьВы должны думать о значении типа M a как о компьютерной программе, которая возвращает значение типа a, а также обменивается данными с состоянием.Суть в том, что для написания любой такой программы достаточно двух операций unit и >>=;весь процесс создания и деконструкции пар (a,s) может быть охвачен этими двумя функциями.