Здравствуйте, Дорогие Хабровчане! Я изучаю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)


  1. csl
    14.12.2021 20:00
    +3

    состояние (!) в чистом языке

    Чистый не потому, что без состояния, а потому, что ссылочно-прозрачный.

    "Функциональное программирование - это не то, что нам рассказывают"

    https://habr.com/ru/post/479238/


    1. sshikov
      14.12.2021 21:49
      +1

      Мне тоже такая формулировка не очень понравилась, если честно. Потому что достаточно открыть скажем википедию, и посмотреть, что такое чистая функция, и там написано:

      В языках программирования чистая функция — это функция, которая:
      является детерминированной;
      не обладает побочными эффектами.


      А чистые языки программирования, там же — это где все функции являются чистыми. И где тут про то, что нет состояния? Нет этого. Так что как минимум, это значит, что нет какого-то общепринятого определения, где написано, что у чистых языков не бывает состояния.


      1. pythonMyLife Автор
        15.12.2021 10:44
        +1

        Хорошо, переформулирую


  1. CrazyOpossum
    15.12.2021 02:44
    +1

    Итак, получили неидиоматичный код на функциональном языке и ворох проблем:

    1) Скорость доступа к переменным О(n). Ок, можно улучшить, если подключить (unordered-)containers. Всё равно не то.

    2) Переменные хранятся в гомогенной коллекции (переменные одного типа). Можно обернуть, но получим слабую типизацию и ошибки в рантайме.

    3) Доступ к переменным по строкам (или любым другим идентификаторам), не определённые переменные вызывают ошибки.

    А главное - зачем это всё?


    1. 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 ())


      1. CrazyOpossum
        15.12.2021 18:19
        +1

        2) Почитайте про heterogeneous lists - например. Вкратце - можно использовать GADTs для сокрытия типа, и при желании сохранить какие-то из его инстансов - как минимум понадобится Typeable. Чтобы извлечь реальные данные придётся использовать Proxy типа и Refl - опять же всё некрасиво и теряем проверки на этапе компиляции, но произвольные данные хранить сможем.

        3) Я имел в виду ошибки логики, а не доступа. В смысле, программист сделал опечатку, и дальше программа работает с Nothing, а не нашими данными.


        1. pythonMyLife Автор
          15.12.2021 19:21
          +1

          Хорошо, спасибо, учту.


  1. koshi
    16.12.2021 18:22

    Значит, к примеру, State Integer () есть функция, преобразовывающая Integer в кортедж ((), Integer)

    Непонятно. State -- это же конструктор типа, как он может быть функцией?
    Что нужно написать в ghci, чтобы :t показало тип функции с указанной сигнатурой?


    1. csl
      16.12.2021 18:42

      Извините, что вмешиваюсь.

      Если я правильно понял именно ваш вопрос (в цитату из поста нужно дольше вчитываться), то так?

      foo :: Integer -> ((), Integer)
      foo age = ((), age)

      GHCi 9.2.1


      1. koshi
        16.12.2021 20:04

        Спасибо. Но у меня вопрос больше про State, а у вас он не фигурирует. Можно как-то типизировать foo как State Integer () ?


    1. 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 не должен стоять конкретный тип?


    1. pythonMyLife Автор
      16.12.2021 21:21
      +1

      Я имею ввиду, что обьект с типом State Integer () будет являться (обёрнутой) ф-ей типа Integer -> ((), Integer), спасибо за вопрос, уточню в статье


      1. koshi
        16.12.2021 22:19
        +1

        Спасибо.
        Проходил летом курс на степике по Haskell Дениса Москвина (первая часть).
        Застрял как раз на монадах. До State правда немного не дошёл.
        На Reader почувстовал, что плыву. Надеялся с помощью вашей статьи сдвинуться с мёртвой точки.

        Переформулирую вопрос выше.
        Вот эта строчка "instance Monad (State s) where"
        в ней s -- типовой параметр. Но s, что идёт далее несёт совсем другой смысл -- это параметр функций.
        Так?
        А совпадение имён чтобы кривую обучения задрать (шутка).

        А когда типовой параметр может пригодиться в определении монады?
        Ведь интерфейс уже задан в классе типов Monad.


        1. pythonMyLife Автор
          16.12.2021 22:29
          +1

          Рад, что помог с пониманием :)

          Использование типовых переменных в определениях инстанса встречается очень часто, чтобы частично применить тип, к примеру кайнд Maybe это * -> *, а необходимый для определения Монады это * -> *, и они совпадают, по этому мы просто определяем инстанс как instance Monad Maybe, а кайнд State есть * -> * -> *, по этому для определения инстанса мы его частично применяем. Про кайнды много рассказать не могу, но мы могу сказать что конкретный тип имеет кайнд *, а контейнеры это как бы функции к типам и имеют тип * -> *. Если будут ещё вопросы, добро пожаловать в личку.