Понимание монадического Фибоначчи

Question

Я изучаю хекел и изучаю монады. Я смотрел и читал различные учебники и закодированы некоторые простые примеры для государственной монады, однако я не могу понять следующий фрагмент кода (взятый из Haskell Wiki):

import Control.Monad.State 
fib n = flip evalState (0,1) $ do 
    forM [0..(n-1)] $ \_ -> do 
    (a,b) <- get 
    put (b,a+b) 
    (a,b) <- get 
    return a 

Мой вопрос сводится к следующему :

1. Что происходит внутри первого утверждения внутреннего do, т.е. то, что приводит (a,b)<-get. Каковы будут значения a и b для конкретного примера.
2. Зачем вам здесь нужна государственная монада?

Answer 1

В этом примере состояние представляет собой пару, содержащую предыдущие два числа, сгенерированные в последовательности. Первоначально это (0, 1) предоставлено evalState.

Тип get является MonadState s m => m s так во внутреннем блоке do

(a, b) <- get 

извлекает состояние пары и связывает a и b к первым и вторым элементами, соответственно. Затем состояние обновляется следующим образом: put.

состояние будет поэтому:

(0, 1), (1, 1), (1, 2), (3, 2), (3, 5), ... 

Наружный

(a, b) <- get 
return a 

распаковывает окончательное значение состояния и возвращает первый элемент.

Answer 2

Сначала давайте проясним используемый алгоритм Фибоначчи. Идея состоит в том, чтобы начать с кортежа (0, 1), а затем найти следующий (1, 0 + 1), следующий как (1, 1 + 1), (2, 2 + 1), (3, 3 + 2) и так далее. Как правило, шаг \(a, b) -> (b, a + b). Вы можете видеть, что в этих кортежах есть числа Фибоначчи.

Что происходит внутри первого утверждения внутренних дел, то есть то, что делает (а, б) < -get привести к?

У Haskell нет утверждений, только выражений.

y <- x не является полным выражением. Он похож на x >>= \y ->.

y <- x 
m 

Является полным выражением и эквивалентно x >>= \y -> m. Линия n, не относящаяся к форме y <- n, эквивалентна _ <- n (за исключением let линий и, возможно, некоторых других я забываю).

Используя это, мы можем обозначить десурацию.

fib n = 
    flip evalState (0, 1) 
    (forM 
     [0..(n-1)] 
     (\_ -> get >>= (\(a, b) -> put (b, a + b))) 
    >>= (\_ -> get >>= (\(a, b) -> return a))) 
) 

Сейчас речь идет просто о понимании >>=, return, get, put, и так далее.

Состояние на самом деле просто функции типа s -> (s, a). Они берут начальное состояние и дают следующее состояние плюс другое значение.

m >>= n a.k.a. "bind" имеет тип Monad m => m a -> (a -> m b) -> m b. Тогда, если наша Монада State s, это то же самое, как:

m >>= n :: 
    ( s -> (s, a)) 
    -> (a -> s -> (s, b)) 
    -> ( s -> (s, b)) 

a возвращаемый m должен быть передан n. Что еще мы можем догадаться? Мы ожидаем, что государство также пройдет, поэтому государство, возвращенное m, должно быть передано также n. Функция m >>= n должна вернуть состояние и значение, которое возвращает n. Затем мы знаем, как осуществить привязку:

m >>= n = uncurry (flip n) . m 

return :: Monad m => a -> m a, который затем эквивалентно return :: a -> s -> (s, a):

return = flip (,) 

get :: State s s эквивалентно get :: s -> (s, s):

get = join (,) 

put :: s -> State s() или put :: s -> s -> (s,()):

put s _ = (s,()) 

evalState :: s -> State s a -> a или evalState :: s -> (s -> (s, a)) -> a:

evalState s f = snd (f s) 

можно развернуть все определения и увидеть то, что происходит в примере. Однако достаточно интуиции.

forM 
    [0..(n-1)] 
    (\_ -> get >>= (\(a, b) -> put (b, a + b))) 

Мы не заботимся о том, число 0 к n - 1 поэтому первый аргумент отбрасывается. get извлекает текущее состояние, затем put записывает новое состояние. Мы делаем это n раз.

>>= (\_ -> get >>= (\(a, b) -> return a))) 

Мы не заботимся о накопленном значении (которое является единицей), и поэтому первый параметр отбрасывается. Затем мы получаем текущее состояние и проектируем только первый элемент пары. Это окончательный ответ, который мы ищем.

flip evalState (0, 1) … 

Наконец Бежим, начиная с начального состояния (0, 1).

Есть некоторые очистки, которые мы можем сделать для этой реализации. Во-первых, нас не волнует диапазон [0..(n-1)], нам просто нужно повторить действие n раз.Более прямой способ сделать это состоит в следующем:

replicateM n (get >>= \(a, b) -> put (b, a + b)) 

Результатом является список блока, который не используется, так что более эффективная версия:

replicateM_ n (get >>= \(a, b) -> put (b, a + b)) 

Существует уже функция для общий шаблон get, за которым следует put с именем modify, который определяется как \f -> get >>= put . f. Поэтому:

replicateM_ n (modify (\(a, b) -> (b, a + b))) 

Тогда есть часть:

>>= (\_ -> get >>= (\(a, b) -> return a))) 

Каждый раз, когда мы не заботимся о предыдущем результате мы можем использовать >>.

>> get >>= (\(a, b) -> return a)) 

Это:

>> get >>= return . fst 

m >>= return . f упрощается fmap f m:

>> fmap fst get 

Теперь у нас есть, в общей сложности:

fib n = 
    evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> fmap fst get 
) 
    (0, 1) 

Мы могли бы также использовать для сравнения :

fib n = 
    fst 
    (evalState 
    ( replicateM_ n (modify (\(a, b) -> (b, a + b))) 
    >> get 
    ) 
    (0, 1) 
) 

А потом, потому что я глупый:

fib = 
    fst 
    . flip evalState (0, 1) 
    . (>> get) 
    . flip replicateM_ (modify (snd &&& uncurry (+))) 

Почему вы хотите использовать государственную монады здесь?

Вы бы этого не сделали. Это понятно, потому что мы используем только значение состояния; другое значение всегда является единицей и отбрасывается. Другими словами, нам нужно только n (то есть номер Фибоначчи, который нужно найти) в начале, а затем нам нужен только накопленный кортеж.

Иногда вы считаете, что есть такая композиция, как h . g . f, но вы хотите отправить два аргумента вместо одного. То есть, когда может применяться State.

Если некоторые функции читаются, а некоторые записывают состояние (второй аргумент) или делают оба, то State подходит для счета. Если есть только читатели, то используйте Reader, и если есть только авторы, используйте Writer.

Мы можем изменить пример, чтобы лучше использовать государственную Монаду. Я заставлю кортеж исчезнуть!

fib = 
    flip evalState 0 
    . foldr (=<<) (return 1) 
    . flip replicate (\x -> get >>= \y -> put x $> x + y) 

Answer 3

Так государство документы: get :: m s -- Return the state from the internals of the monad (см here).

Но я очень хорошо помню, что, когда я пытался обернуть голову вокруг государственной Монады, это не помогло мне.

Я могу только порекомендовать играть с :i и :t в ghci и тестировать различные подвыражения. Просто чтобы почувствовать это. Немного как это:

import Control.Monad.State.Lazy 

runState (get) 0 
runState (get >>= \x -> put (x+1)) 0 
:t return 1 :: State Int Int 
runState (return 1) 0 
runState (return 1 >>= \x -> (get >>= \y -> return (x+y))) 0 

-- Keeping a pair of (predecessor/current) in the state: 
let f = (get >>= (\(a,b) -> put (b,a+b))) :: State (Int, Int)() 
runState (f >> f >> f >> f >> f >> f) (0,1) 

-- only keeping the predecessor in the state: 
let f x = (get >>= (\y -> put x >> return (x+y))) :: State Int Int 
runState (return 1 >>= f >>= f >>= f >>= f >>= f >>= f) 0 

Также поиграйте с modify, runState, evalState, execState.