(no subject)
Jun. 6th, 2007 05:01 pmЗадача
Итак, наша задача - смонтировать императивное состояние чисто функциональными средствами. Состояние должно иметь тип (обозначим его через S). В дальнейшем, для простоты мы будем предполагать, что
type S = Int
однако будем писать S, чтобы не терять общности. Важно, что это конкретный, неполиморфный тип – мы же не хотим, чтобы в процессе вычисление состояние было то Int, то Char, то String?
Каков должен быть интерфейс для работы с состоянием? Мы должны уметь изменять это состояние (update) и считывать его значение (read). Ясно, что такое изменяемое состояние может жить только внутри монады; обзовём тип этого монадического контейнера SM, тогда:
readSM :: SM S
updateSM :: (S -> S) -> SM ()
Действие readSM возвращает текущее состояние упакованное в монаду, действие updateSM принимает функцию, изменяющую состояние и выполняет её, не возвращая ничего интересного. Монада на выходе необходима, поскольку эти функции (действия) будут использоваться внутри монадического вычисления.
Чуть-чуть про монадические вычисления
Напомним определение монады
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
Что они нам дают? Во-первых, они позволяют организовывать цепочку вычислений:
e1 >> e2 >> e3 >> e4
В засахаренном виде это выглядит так
do e1; e2; e3; e4
Более интересно, однако, то, что можно вытаскивать из выражения запакованное в монаду значение и использовать его где-то в дальнейших монадических вычислениях
e1 >>= \p -> e2 >> e3 >> e4
что под сахаром выглядит как
do p <- e1; e2; e3; e4
То есть внутри выражений e2, e3 и e4 мы можем обращаться к распакованному p.
State Monad
Для нашей монады SM это может выглядеть так
do x <- readSM
updateSM (+1)
y <- readSM
return (x, y)
Теперь x будет связано с исходным состоянием, а y – с увеличенным на 1. Фактически это уже и есть ожидаемый “императивный” код. В дальнейшем монадическом вычислении мы можем использовать значения x и y как угодно (в примере мы возвращаем пару (x, y)).
Более того, мы можем написать код, который выглядит, как связывание переменной с мутирующим состоянием! Вот то, что так смутило![[profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
geniepro:
do x <- readSM
updateSM (+1)
x <- readSM
return x
Опля! “Пишем” в “переменную” x? Чистой воды иллюзия. Рассахарим это дело:
readSM >>= \x -> updateSM (+1) >> readSM >>= \x -> return x
Понятно, в чём фишка? Тут просто два разных икса, а конфликта мы избегаем благодаря разным областям видимости. В return, естественно, отправляется x из внутренней (вложенной) лямбды. Без сахара это, однако, выглядит полностью идентично мутирующей переменной.
Как устроена монада состояния внутри?
Конспективно это изложено в GIH (9.3), подробно – в книжке Душкина.
Технические замечания.
1. Говоря про монады, я для простоты изложения полностью игнорировал fail.
2. На самом деле конструкция
do p <-e1; e2; e3; e4
при трансляции рассахаривается не в лямбду
e1 >>= \p -> e2 >> e3 >> e4
а в let-выражение
let e p = do {e2 >> e3 >> e4}
in e1 >>= e
Это связано с тем, что в отличии от лямбды, где связывание мономорфизирует переменную, let-выражения полностью сохраняют полиморфизм. (см. параграф 3.14 Haskell98 Report, rev.2002)
Итак, наша задача - смонтировать императивное состояние чисто функциональными средствами. Состояние должно иметь тип (обозначим его через S). В дальнейшем, для простоты мы будем предполагать, что
type S = Int
однако будем писать S, чтобы не терять общности. Важно, что это конкретный, неполиморфный тип – мы же не хотим, чтобы в процессе вычисление состояние было то Int, то Char, то String?
Каков должен быть интерфейс для работы с состоянием? Мы должны уметь изменять это состояние (update) и считывать его значение (read). Ясно, что такое изменяемое состояние может жить только внутри монады; обзовём тип этого монадического контейнера SM, тогда:
readSM :: SM S
updateSM :: (S -> S) -> SM ()
Действие readSM возвращает текущее состояние упакованное в монаду, действие updateSM принимает функцию, изменяющую состояние и выполняет её, не возвращая ничего интересного. Монада на выходе необходима, поскольку эти функции (действия) будут использоваться внутри монадического вычисления.
Чуть-чуть про монадические вычисления
Напомним определение монады
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a
Что они нам дают? Во-первых, они позволяют организовывать цепочку вычислений:
e1 >> e2 >> e3 >> e4
В засахаренном виде это выглядит так
do e1; e2; e3; e4
Более интересно, однако, то, что можно вытаскивать из выражения запакованное в монаду значение и использовать его где-то в дальнейших монадических вычислениях
e1 >>= \p -> e2 >> e3 >> e4
что под сахаром выглядит как
do p <- e1; e2; e3; e4
То есть внутри выражений e2, e3 и e4 мы можем обращаться к распакованному p.
State Monad
Для нашей монады SM это может выглядеть так
do x <- readSM
updateSM (+1)
y <- readSM
return (x, y)
Теперь x будет связано с исходным состоянием, а y – с увеличенным на 1. Фактически это уже и есть ожидаемый “императивный” код. В дальнейшем монадическом вычислении мы можем использовать значения x и y как угодно (в примере мы возвращаем пару (x, y)).
Более того, мы можем написать код, который выглядит, как связывание переменной с мутирующим состоянием! Вот то, что так смутило
geniepro: do x <- readSM
updateSM (+1)
x <- readSM
return x
Опля! “Пишем” в “переменную” x? Чистой воды иллюзия. Рассахарим это дело:
readSM >>= \x -> updateSM (+1) >> readSM >>= \x -> return x
Понятно, в чём фишка? Тут просто два разных икса, а конфликта мы избегаем благодаря разным областям видимости. В return, естественно, отправляется x из внутренней (вложенной) лямбды. Без сахара это, однако, выглядит полностью идентично мутирующей переменной.
Как устроена монада состояния внутри?
Конспективно это изложено в GIH (9.3), подробно – в книжке Душкина.
Технические замечания.
1. Говоря про монады, я для простоты изложения полностью игнорировал fail.
2. На самом деле конструкция
do p <-e1; e2; e3; e4
при трансляции рассахаривается не в лямбду
e1 >>= \p -> e2 >> e3 >> e4
а в let-выражение
let e p = do {e2 >> e3 >> e4}
in e1 >>= e
Это связано с тем, что в отличии от лямбды, где связывание мономорфизирует переменную, let-выражения полностью сохраняют полиморфизм. (см. параграф 3.14 Haskell98 Report, rev.2002)
