Изменяемые переменные через монаду State на Haskell

Здравствуйте, Дорогие Хабровчане! Я изучаюHaskell, и для закрепления материала я, используя монадуState, реализовал полноценные переменные! Я человек и могу ошибиться, пожалуйста, поправляйте меня в комментариях. Также будет очень приятно услышать конструктивную критику.

class Monad m where -- Определение Монады для типа m   (>>=)  :: m a -> (  a -> m b) -> m b   -- Применяет ф-ию к текущему монадическому значению    (>>)   :: m a ->  m b         -> m b   -- "Заменяет" текущее монадическое значение    return ::   a                 -> m a   -- Оборачивает значение в минимальный контекст.      x >> y = x >>= \_ -> y -- Определение по-умолчанию.

Основы: кто такая монада State?

Незнающий человек может удивиться: как так, состояние (!) в чистом языке! Однако, хитрые хаскелисты с лёгкостью сделали «невозможное». Для начала,Stateимеет следующее определение:

newtype State s a = State { runState :: s -> (a, s)}

Значит, к примеру, State Integer () есть функция, преобразовывающая Integer в кортедж ((), Integer). Подсказываю:s — состояние, а a — значение. «Но, это не монада!», возразите Вы, и будете правы, вот реализация Состояния как Монады:

instance Monad (State s) where return x = State $ \s -> (x, s) (State h) >>= f = State $ \s ->  let (a, newState) = h s (State g) = f a in g newState      -- x >> y = x >>= \_ -> y

return x, как положено, помещает значение в минимальный контекст, т. е. в данном случае мы заменяем текущее значение a(результат вычислений), а состояние оставляем прежним. В случае привязки немного сложней: используя pattern matching, производится извлечение функции из состояния (h), и далее оборачивается в состояние анонимная функция, принимающая состояние s и возврающая g newState, где newState — состояние, полученное вызовом h s, а g — функция, полученная «разворачиванием» вызова f a. Получается, мы заменяем текущее состояние (т. е. функцию) новым, «наращивая» слои. Также здесь я показал обычную реализацию >>.

import Control.Monad.State  set_state :: s -> State s () set_state s = state $ \_ -> ((), s)      get_state :: State s s get_state = state $ \s ->     (s, s)    main' :: State Integer Integer main' = do     set_state 10     state' <- get_state     return state'    -- Аналогично этому: main'' = set_state 10 >> (get_state >>= \state' -> return state') -- Аналогично этому: main''' = set_state 10 >>= \_ -> get_state >>= \state' -> return state'

В функцияхset_ get_ -state мы оборачиваем анонимную функцию, принимающую текущее состояние, в state, а возвращает новое состояние в связке с новым значением. Далее мы используем эти функции в main' используя do-нотацию. Также я показал что находится «под капотом» этого синтаксического сахара. Далее пошагово раскроемы вызовы bind оператора:

main' = set_state 10 >>= \_ -> get_state >>= \state' -> return state'  -- Вычисляем функции get_ и set_ -state, убираем блок с return (излишество) main2 = state (\_ -> ((), 10)) >>= \_ -> state (\s -> (s, s))  -- "Разворачиваем" вызовы >>= оператора main3 = State $ \s -> let (a, newState) = (\_ -> ((), 10)) s     (State g) = (\_ -> state (\s -> (s, s))) a     in g newState      -- Вычисляем лямда-функции main4 = State $ \s -> let (a, newState) = ((), 10)     (State g) = state (\s -> (s, s))     in g newState      -- Подставляем значения в pattern matching main5 = State $ \s -> let a = ()   newState = 10              g = \s -> (s, s)   in g newState    -- * Для вычисления этого требуется "достать" ф-ию из State, --   для этого используется runState (см. определение State) -- Подставляем переменные main6 = (\s -> (s, s)) 10  -- Вычисляем и эту лямбду main7 = (10, 10)

Вот мы выполнили «грязную работу» компилятора. Надеюсь так станет яснее.

Переменные?

Теперь, разобравшись с магией чистого состояния, двигаемся дальше, к переменным. Я собираюсь хранить список переменных как состояние, а сама переменая есть обёртка вокруг кортеджа из имени и значения. К сожалению, таким образом у нас все переменные будут одного типа, однако это не столь проблематично.

import qualified Control.Monad.State as S  newtype Var name val = Var {runVar :: (name, val)} -- Переменная - обёртка                                                     -- вокруг кортеджа. type Vars name val = [Var name val]                       -- | type VarState name val res = S.State (Vars name val) res  -- | Для удобства. type VarEnv val = VarState String val (Maybe val)         -- |

Здесь определяется новый тип — обёртка Var, И вспомогательные псевдонимы типов Vars (список переменных), VarState(на замену State) и VarEnv(как надстройка VarState, о нём попозже). Далее я определяюVarкак экземпляр тайпклассов Showи Eq:

instance (Show name, Show val) => Show (Var name val) where     show (Var (name, val)) = "Var " ++ show name ++ " = " ++ show val  instance (Eq name, Eq val) => Eq (Var name val) where         Var (name, val) == Var (name', val') = (name == name') && (val == val')

Тайпкласс Show— обьекты отображаемые в строку, Тайпкласс Eq— обьекты которые можно сравнивать (==, /=). Далее, я определяю вспомогательные функции для Var:

varName :: Var name val -> name varName = fst . runVar  varVal :: Var name val -> val varVal = snd . runVar  var :: name -> val -> Var name val var name val = Var (name, val)  runVars vars = S.runState vars []  -- Для упрощения запуска, потом применяется как: -- runVars $ do --     ... -- Действия с переменными (см. дальше)

Функция varнужна чтобы не писать скобки кортеджа как Var (name, value). Далее самое интересное: работаем с переменными. Что мы можем сделать с переменными? Изменить (в т. ч. добавить), получить, удалить. Для реализации можно просто рекурсивно проходиться по списку переменных и делать сопутствующее действие, к примеру, перезаписывать:

-- Присваивание переменной -- Ф-ия для присвоения по имени и значению, обёртка  -- вокруг присвоения по обьекту переменной: assign :: Eq name => name -> val -> VarState name val () name `assign` val = assignV $ var name val -- Ф-ия для присвоения по обьекту переменной, строит состояние -- вокруг самого присваивания. assignV :: Eq name => Var name val -> VarState name val ()  assignV var = S.state $     \vars -> ((), vars `assignV'` var) -- Само присваивание. Никак не относится к состоянию. assignV' :: Eq name => Vars name val -> Var name val -> Vars name val assignV' ((cvar@(Var (cname, _))):xs) (var@(Var (name, _)))     | cname == name = var:xs      -- Если имя проверяемой переменной и задаваемой равны, то заменить     -- проверяемую переменную задаваемой.     | otherwise = cvar:(xs `assignV'` var)     -- Иначе "оставить просматриваемую переменную в покое" и продолжать искать.  assignV' [] var = [var] -- Если переменная с одинаковым именем не найдена, создать новую.

Получение значения переменной:

-- Получение переменной по имени, заботится об состоянии. -- Важно, что результат может закончится ничем (нет такой переменной), -- по этому результат -- Maybe val. get :: Eq name => name -> VarState name val (Maybe val) get name = S.state $     \vars -> (vars `get'` name, vars)  -- Получение переменной из списка. Никак не относится к окружению. get' :: Eq name => Vars name val -> name -> Maybe val get' ((Var (cname, val)):xs) name     | cname == name = Just val      -- Если имя проверяемой и получаемой переменных равны, то     -- то вернуть её значение, обёрнутое в Just     | otherwise = xs `get'` name     -- Иначе продолжать искать.   get' [] _ = Nothing -- Если ничего не нашли то возвращаем Nothing.

А теперь удаление переменной. Не отрицаю, чуть — чуть кривое:

-- Основная функция, управляет состоянием. del :: Eq name => name -> VarState name val (Maybe ()) del name = S.state $ -- Обёртка вокруг del'     \vars -> vars `del'` name  -- Ф-ия, удаляющая переменную с таким же именем. -- Результат тоже Maybe (), т. к. нельзя удалить переменную, -- которой нет. del' :: Eq name => Vars name val -> name -> (Maybe (), Vars name val) del' [] _ = (Nothing, []) -- Нельзя удалить переменную, которй нет. del' (cvar@(Var (cname, _)):xs) name     | cname == name = (Just (), xs)      -- Если имена проверяемой и удаляемой переменных равны, то возвращаем     -- список переменных (без удалённой) и Just (), показывающий нам,     -- что операция проведена успешно.     | otherwise = (res, cvar:vars) where (res, vars) = xs `del'` name     -- Иначе возвращаем список переменных с проверенной и рекурсивно      -- проверяем следующие.

Ох, вроде всё. Теперь посмотрим на всё это великолепие в коде:

import qualified Vars as V  main :: IO () main = print . runVar $ vars_stuff  vars_stuff :: V.VarEnv Integer vars_stuff = do     init_vars     b <- V.get "VarB"      V.del "VarB"      return b  init_vars :: V.VarState String Integer () init_vars = do     "VarA" `V.assign` 10     "VarB" `V.assign` 42     "VarC" `V.assign` 33      -- Результат: (Just 42, [Var "VarA" = 10,Var "VarC" = 33])

Также, я обещал рассказать про используемый здесь VarEnv val. Т. к. в большинстве случаев имя — строка, а результат —Maybeтипа переменной, то для упрощения я создал этот псевдоним типа.

Поздравляю, мы сделали это! Мне было очень интересно работать над этим проектом, и теперь я предлагаю вам, Моим Читателям, для тренировки, реализовать переменные по памяти. Спасибо за прочтение, я очень признателен Вам.

module Vars (     VarState,     VarEnv,      assign,     get,     del,      var,     varName,     varVal,      runVars ) where  import qualified Control.Monad.State as S  newtype Var name val = Var {runVar :: (name, val)}  type Vars name val = [Var name val] type VarState name val res = S.State (Vars name val) res type VarEnv val = VarState String val (Maybe val)  instance (Show name, Show val) =>          Show (Var name val) where     show (Var (name, val)) =          "Var " ++ show name ++ " = " ++ show val  instance (Eq name, Eq val) =>          Eq (Var name val) where         Var (name, val) == Var (name', val') =             (name == name') && (val == val')  varName :: Var name val -> name varName = fst . runVar  varVal :: Var name val -> val varVal = snd . runVar  var :: name -> val -> Var name val var name val = Var (name, val)  assign :: Eq name => name -> val -> VarState name val () name `assign` val = assignV $ var name val  assignV :: Eq name => Var name val -> VarState name val ()  assignV var = S.state $     \vars -> ((), vars `assignV'` var)  assignV' :: Eq name => Vars name val -> Var name val -> Vars name val assignV' ((cvar@(Var (cname, _))):xs) (var@(Var (name, val)))     | cname == name = (var):xs     | otherwise = cvar:(xs `assignV'` var)  assignV' [] var = [var]  get :: Eq name => name -> VarState name val (Maybe val) get name = S.state $     \vars -> (vars `get'` name, vars)  get' :: Eq name => Vars name val -> name -> Maybe val get' ((Var (cname, val)):xs) name     | cname == name = Just val     | otherwise = xs `get'` name  get' [] _ = Nothing  del :: Eq name => name -> VarState name val (Maybe ()) del name = S.state $     \vars -> vars `del'` name  del' :: Eq name => Vars name val -> name -> (Maybe (), Vars name val) del' [] _ = (Nothing, []) del' (cvar@(Var (cname, _)):xs) name     | cname == name = (Just (), xs)     | otherwise = (res, cvar:vars) where (res, vars) = xs `del'` name  runVars vars = S.runState vars []