Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Здравствуйте, Дорогие Хабровчане! Я изучаюHaskell
, и для закрепления материала я, используя монадуState
, реализовал полноценные переменные! Я человек и могу ошибиться, пожалуйста, поправляйте меня в комментариях. Также будет очень прятно услышать конструктивную критику.
Основы: кто такая монада State?
Незнающий человек может удивиться: как так, состояние (!) в чистом языке! Однако хитрые хаскелисты с лёгкостью сделали "невозможное". Для начала,State
имеет такое определение:
newtype State s a = State { runState :: s -> (a, s)}
Ага, т. е., к примеру, State 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
, который имитирует конструктор 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 (varname, varvalue)
. Далее самое интересное: работаем переменными. Что мы можем сделать с переменными? Изменить (в т. ч. добавить), получить, удалить. Как же нам это реализовать? Будем рекурсивно проходиться по списку переменных и делать сопутствующее действие, к примеру, перезаписывать.
-- Присваивание переменной
-- Ф-ия для присвоения по имени и значению, обёртка
-- вокруг присвоения по обьекту переменной:
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]
-- Если переменная с одинаковым именем не найдена, создать новую.
Получение значения переменной:
-- Получение переменной по имени, заботится об состоянии.
-- Важно, что результат может закончится ничем (нет такой переменной),
-- по этому результат - 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 -- Если имя просматриваемой и необходимой
-- переменных одинаковое, вернуть обёрнутое в
-- Maybe значение переменной
| 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 []