Блог

Я пытаюсь изучить некоторые основы государственной монады в Haskell, создавая свои собственные примеры.

Рассмотрим простой пример, в котором я хочу подсчитать количество четных целых чисел в массиве целых чисел. Конечно, это можно сделать очень легко, используя чистые функции, но я хотел попробовать маршрут с круговым движением по State monad, где мы сохраняем счетчик, который продолжает увеличиваться для каждого проверенного элемента.

Вот частичная (но явно неправильная) попытка, которую мне удалось придумать до сих пор.

 import Control.Monad.State

f' :: [Int] -> State Int [Int]
f' []     = state (s -> ([],s)) 
f' (x:xs) = if x `mod` 2 == 0 then state (s -> ((x:xs), s 1)) -- how can I fix this line? 
            else f' xs
  

Этот код компилируется, но явно не дает правильного ответа. Как тогда я могу исправить этот код, чтобы сделать что-то похожее на следующий код Python

 counter = 0 # incremented when we encounter an even integer.
for elt in integer_list:
   if elt % 2 == 0 :
      counter = counter   1 
  

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

На мой взгляд, реальная проблема заключается в том, что вы выполнили рекурсию только в одной ветви вашего if . Чего мы действительно хотим, так это повторить, является ли текущий элемент четным. Так что:

 f' (x:xs) = do
    if x `mod` 2 == 0 then state (s -> ((), s 1)) -- increase the count by one
                      else state (s -> ((), s  )) -- don't increase the count by one
    rest <- f' xs -- compute the answer for the rest of the list
    return (x:rest) -- reconstruct the answer for the whole list
  

Мы можем проверить, что он делает правильные вещи в ghci:

 > runState (f' [1..5]) 0
([1,2,3,4,5],2)
  

Это лишь самое маленькое изменение, которое вы можете внести, чтобы ваша идея реализации заработала.

Исходя из этого, я бы предложил ряд рефакторингов. Во-первых, ваше повсеместное использование state — это запах кода. Вместо этого я бы написал различные варианты использования таким образом:

 f' [] = return []
f' (x:xs) = do
    if x `mod` 2 == 0 then modify ( 1) else return ()
    rest <- f' xs
    return (x:rest)
  

Отсюда я бы использовал even функцию в условном выражении и заметил, что when функция реализует операцию «выполнить какое-либо действие или return () «. Итак:

 f' [] = return []
f' (x:xs) = do
    when (even x) (modify ( 1))
    rest <- f' xs
    return (x:rest)
  

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

 f' xs = mapM (x -> when (even x) (modify ( 1)) >> return x) xs
  

Наконец, я думаю, что немного странно, что функция возвращает список, который она использовала. Само по себе не однотипно, как и предыдущие возражения, но, возможно, не то, что вы хотите. Если окажется, что вы не планируете использовать полученный список в каких-либо последующих вычислениях, будет эффективнее выбросить его по ходу дела; и mapM_ комбинатор делает это. Итак:

 f' :: [Int] -> State Int ()
f' xs = mapM_ (x -> when (even x) (modify ( 1))) xs
  

На данный момент я бы счел f' довольно хорошей реализацией предложенной вами идеи.

Давайте вернемся к чертежной доске. Фактическая функция, которую вы хотите использовать, выглядит примерно так

 countEven :: [Int] -> Int
countEven xs = runStateMagic xs
  

где runStateMagic использует некоторые State скрытые в его глубинах. Как может выглядеть эта функция? Ну, он должен использовать либо execState или evalState . Поскольку нас интересует только состояние (иначе говоря, наше текущее количество чисел), давайте заменим runStateMagic на execState :

 countEven :: [Int] -> Int
countEven xs = execState someState 0
  

Теперь execState тип исправляет наше stateFunc значение State Int a . Фактический тип значения состояния произвольный, поскольку мы все равно не собираемся его использовать. Итак, что же someState делать? Вероятно, это должно работать в списке и использоваться modify' ( 1) , если у нас есть четное число. Давайте напишем помощник для этого:

 increaseIfEven :: Int -> State Int ()
increaseIfEven n
  | even n    = modify' inc
  | otherwise = return ()
  

Теперь это изменит состояние, если число было четным. Все, что нам нужно сделать, это применить это к каждому элементу в списке. Поэтому для списка xs мы можем просто сделать

 mapM_ increaseIfEven xs
  

Помните, mapM_ :: (a -> m b) -> [a] -> m () . Но в нашем случае, то m есть State Int , так что он уже содержит наш счетчик.

В целом, мы получаем

 countEven :: [Int] -> Int
countEven xs = execState (mapM_ increaseIfEven xs) 0
  

Но имейте в виду: важной частью было исправить тип исходной функции, f' .