Во-первых, на данном этапе процесса обучения вам, вероятно, не стоит беспокоиться о «побочных эффектах».Также вы пытаетесь смешать две монады, State и IO, в точке, где вы, кажется, тоже не освоили.Таким образом, вы, вероятно, должны принять это проще.
В монаде IO можно выполнять действия с состоянием, используя IORefs, который можно рассматривать как изменяемые переменные.Если бы я был тобой, я бы не пошел туда только сейчас.Затем есть монада State, которая, грубо говоря, является удобным способом имитации функций с состоянием в чистом виде.
Теоретически вы можете думать о функции с состоянием f :: a -> b как о чистой функции типа f :: (a,s) -> (b,s), где s представляет некоторое состояние, к которому вы можете обращаться и изменять.Вышеприведенное не совсем подходит для структуры монады, потому что в монаде m мы хотим, чтобы a -> m b представлял эффективные функции от a до b.Но это легко адаптироваться.Тип (a,s) -> (b,s) может быть не потрачен на получение a -> s -> (b,s), и мы принимаем m b как s -> (b,s), поэтому a -> m b представляет a -> s -> (b,s).
Так вот, что представляет собой монада State s.Для каждого типа b тип State s b равен s -> (b,s), что можно прочитать как «дай мне пропущенное начальное состояние s, чтобы я мог вычислить b и конечное состояние s.функция с состоянием a -> State s b - это a -> s -> (b,s), которая может быть прочитана как "эта функция берет a и производит вычисление, которое при начальном состоянии s дает результат b и конечное состояние s.
Это просто чтобы дать вам общее представление о том, как это работает.Теперь вот код, который делает то, что вы хотите.Давайте начнем с простого подхода.
size :: [Int] -> State Int ()
size [] = put 0
size (x:xs) = do size xs
num <- get
put (num + 1)
Типом является State Int (), потому что вы просто обновляете целочисленное состояние и не возвращаете значение (это все, что нам нужно).
Процедура очень похожа на обычную рекурсивную функцию для вычисления размера (без аккумулятора), но мы выполняем эту работу путем обновления состояния.Чтобы запустить этот пример, просто наберите
runState (size list) 0
для некоторых list.Обратите внимание, что 0, который является начальным состоянием, здесь не имеет значения, потому что алгоритм работает, устанавливая состояние как 0 для пустого списка, затем добавляя 1 для каждого элемента.
Теперь версия, которая работает накапливающимся образом,
sizeAc :: [Int] -> State Int ()
sizeAc [] = return ()
sizeAc (x:xs) = do num <- get
put (num + 1)
sizeAc xs
Снова, чтобы запустить этот пример, просто сделайте,
runState (sizeAc list) 0
Обратите внимание, в этом случае вы должны использовать 0 в качестве исходного состояния.Функция выполняет для каждого элемента списка обновление состояния, добавляя единицу к значению состояния.Для пустого списка это ничего не делает.
Наконец версия с map, так как она появляется в вашей первоначальной попытке.Сначала мы реализуем действие подсчета.
count :: State Int ()
count = do num <- get
put (num + 1)
Это действие состоит в получении доступа к состоянию и обновлении его с добавленным юнитом.Затем создайте список таких действий для каждого элемента в списке.
sizeAux' :: [Int] -> [State Int ()]
sizeAux' xs = map (\x -> count) xs
Обратите внимание, тип результата - список.Результатом является список, в котором все элементы имеют действие count.Затем мы выполняем эти действия последовательно, используя sequence_, тип которого указан ниже (специализируется для списков и для нашей конкретной монады).
sequence_ :: [m a] -> m ()
sequence_ :: [State Int ()] -> State Int ()
Результирующая функция:
size' :: [Int] -> State Int ()
size' xs = sequence_ (sizeAux' xs)
, которую снова можно запустить,
runState (size' list) 0
и еще раз отметьте, что здесь важно начальное состояние 0,
На данный момент это может показаться несколько сложным.Вам нужно будет лучше понять класс монады, обозначения do и особенности государственной монады.В любом случае это то место, куда вы должны идти, не смешивая State с IO.