Здравствуйте, Дорогие Хабровчане! Я изучаюHaskell
, и для закрепления материала я, используя монадуState
, реализовал полноценные переменные! Я человек и могу ошибиться, пожалуйста, поправляйте меня в комментариях. Также будет очень приятно услышать конструктивную критику.
Для тех, кто не знает синтаксис Haskell, и его особенностей.
Сейчас я выделю несколько важных аспектов:
Haskell
- статически типизированный, функциональный декларативный язык.Все ф-ии чистые. Это хорошо и удобно.
-
Так весь код - вызов функций, то для вызова функции не требуется скобок:
-- Декларация типа функции. В большинстве случаев не необходима. -- someFunc (Int, Int) -> Int -- *Пояснение к аннотации типа. someFunc :: Int -> Int -> Int -- Тело функции, оно может быть определено несколько раз: someFunc 0 0 = 42 someFunc arg arg' = arg + arg'
Названия "переменных" могут содержать штрих:
arg'
.Все "переменные" - на самом деле константы, и сегодня я буду реализовывать переменные изменяемые.
-
Операторы и функции - одно и тоже, мы можем определить оператор самостоятельно:
-- Декларация типа ф-ии (+) -- Операторы пишутся в таких случаях в скобках (+) :: Num a => a -> a -> a -- Про => см. далее. -- Использование операторов как функций: (+) 1 3 -- Использование ф-ий как операторов (в инфиксной форме): 4 `div` 2
Также во всевозможных декларациях типов можно встретить в начале что - то типа
(Num a, Integral b, Show q, Eq s, ...) =>
Это значит что в последующей декларации типа типовая переменная реализует какой-либо Тайпкласс (класс типов), в примере,a
реализует тайпкласс Num,b
- тайпклассIntegral
...Класс типов это что - то вроде интерфейса. Но это примерное определение.
-
Парочка операторов, для понимания кода:
-- (.) - Оператор композиции ф-ий: (.) :: (b -> c) -> (a -> b) -> (a -> c) (f . g) x = f (g x) -- ($) - Оператор вызова ф-ии. Имеет наименьший приоритет, -- а также правоассациотивен. -- (В то время, как обычный вызов ф-ии - наибольший.) ($) :: (a -> b) -> a -> b f $ a = f a -- (:) - Cons оператор, добавляет в начало списка элемент: -- 1:[2, 3] === [1, 2, 3]
-
Я думаю, Вы и так поняли, что я что-то недоговариваю. Все ф-ии в этом замечательном языке по умолчанию каррированны:
f :: Num a => a -> a -> a f a b = a + b -- "Съели" один аргумент. g :: Num a => a -> a g' :: Num a => a -> a g x = f 5 x -- Воспользуемся так называемой "бесточечной нотацией": g' = f 5 -- Убрали "точку" аргумент x с обоих сторон.
-
Также в
Haskell
есть приятный синтаксис для создания лямбда-функций (т. е. анонимных):f :: Num a => a -> a -> a f a b = a + b f = \a b -> a + b -- Используем лямбду.
Если будут вопросы по синтаксису: добро пожаловать в комментарии и ЛС.
Да кто такие эти ваши монады!?
Монады - это Тайпкласс (см. прошлый раздел) для оборачиваемых типов, вот его определение:
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 -- Определение по-умолчанию.
Для Монад также была придумана do-нотация
, "склеивающая" всё что в ней есть с помощью >>
Основы: кто такая монада 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'
Разница между state и State
State
- конструктор типа State
, однако по умолчанию он не экспортируется, и для публичного использования предлагается ф-ия 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 []
Комментарии (14)
CrazyOpossum
15.12.2021 02:44+1Итак, получили неидиоматичный код на функциональном языке и ворох проблем:
1) Скорость доступа к переменным О(n). Ок, можно улучшить, если подключить (unordered-)containers. Всё равно не то.
2) Переменные хранятся в гомогенной коллекции (переменные одного типа). Можно обернуть, но получим слабую типизацию и ошибки в рантайме.
3) Доступ к переменным по строкам (или любым другим идентификаторам), не определённые переменные вызывают ошибки.
А главное - зачем это всё?
pythonMyLife Автор
15.12.2021 09:23+3Это проект был создан а обучательных целях, конечно, его никто не будет использовать в реальных целях, в Хаскеле они просто не нужны.
Согласен с 1), но как разработчик в т. ч. на Python мне не столь критичны несколько лишних десятков миллисекунд, повторюсь этот проект в создан обучательных целях.
Со 2) думал, ничего лучше не придумал создавать тип как
VarVal = IntVal Int | StrVal String
...С 3) я разобрался используя типы
Maybe
, вот сигнатуры публичныхget
иdel
ф-ийget :: Eq name => name -> VarState name val (Maybe val) del :: Eq name => name -> VarState name val (Maybe ())
CrazyOpossum
15.12.2021 18:19+12) Почитайте про heterogeneous lists - например. Вкратце - можно использовать GADTs для сокрытия типа, и при желании сохранить какие-то из его инстансов - как минимум понадобится Typeable. Чтобы извлечь реальные данные придётся использовать Proxy типа и Refl - опять же всё некрасиво и теряем проверки на этапе компиляции, но произвольные данные хранить сможем.
3) Я имел в виду ошибки логики, а не доступа. В смысле, программист сделал опечатку, и дальше программа работает с Nothing, а не нашими данными.
koshi
16.12.2021 18:22Значит, к примеру, State Integer () есть функция, преобразовывающая Integer в кортедж ((), Integer)
Непонятно. State -- это же конструктор типа, как он может быть функцией?
Что нужно написать в ghci, чтобы :t показало тип функции с указанной сигнатурой?csl
16.12.2021 18:42Извините, что вмешиваюсь.
Если я правильно понял именно ваш вопрос (в цитату из поста нужно дольше вчитываться), то так?
foo :: Integer -> ((), Integer)
foo age = ((), age)GHCi 9.2.1
koshi
16.12.2021 20:04Спасибо. Но у меня вопрос больше про State, а у вас он не фигурирует. Можно как-то типизировать foo как State Integer () ?
koshi
16.12.2021 20:20И вот я в новом файле, не импортируя стандартный Control.Monad.State, написал код из статьи:
newtype State s a = State { runState :: s -> (a, s)}
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При попытки компиляции получаю ошибку:
• No instance for (Applicative (State s))
arising from the superclasses of an instance declaration
• In the instance declaration for ‘Monad (State s)’
|
2 | instance Monad (State s) where
| ^^^^^^^^^^^^^^^
Failed, no modules loaded.И вообще не понял эту строчку
instance Monad (State s) where
Разве здесь вместо параметра s не должен стоять конкретный тип?
pythonMyLife Автор
16.12.2021 21:21+1Я имею ввиду, что обьект с типом State Integer () будет являться (обёрнутой) ф-ей типа Integer -> ((), Integer), спасибо за вопрос, уточню в статье
koshi
16.12.2021 22:19+1Спасибо.
Проходил летом курс на степике по Haskell Дениса Москвина (первая часть).
Застрял как раз на монадах. До State правда немного не дошёл.
На Reader почувстовал, что плыву. Надеялся с помощью вашей статьи сдвинуться с мёртвой точки.Переформулирую вопрос выше.
Вот эта строчка "instance Monad (State s) where"
в ней s -- типовой параметр. Но s, что идёт далее несёт совсем другой смысл -- это параметр функций.
Так?
А совпадение имён чтобы кривую обучения задрать (шутка).А когда типовой параметр может пригодиться в определении монады?
Ведь интерфейс уже задан в классе типов Monad.pythonMyLife Автор
16.12.2021 22:29+1Рад, что помог с пониманием :)
Использование типовых переменных в определениях инстанса встречается очень часто, чтобы частично применить тип, к примеру кайнд Maybe это * -> *, а необходимый для определения Монады это * -> *, и они совпадают, по этому мы просто определяем инстанс как instance Monad Maybe, а кайнд State есть * -> * -> *, по этому для определения инстанса мы его частично применяем. Про кайнды много рассказать не могу, но мы могу сказать что конкретный тип имеет кайнд *, а контейнеры это как бы функции к типам и имеют тип * -> *. Если будут ещё вопросы, добро пожаловать в личку.
csl
Чистый не потому, что без состояния, а потому, что ссылочно-прозрачный.
"Функциональное программирование - это не то, что нам рассказывают"
https://habr.com/ru/post/479238/
sshikov
Мне тоже такая формулировка не очень понравилась, если честно. Потому что достаточно открыть скажем википедию, и посмотреть, что такое чистая функция, и там написано:
А чистые языки программирования, там же — это где все функции являются чистыми. И где тут про то, что нет состояния? Нет этого. Так что как минимум, это значит, что нет какого-то общепринятого определения, где написано, что у чистых языков не бывает состояния.
pythonMyLife Автор
Хорошо, переформулирую