Государство Монад никогда не заканчивается

Question

Не мог бы рассказать мне, почему этот фрагмент кода, который использует государственную монаду, никогда не заканчивается?

fib' :: State [Int]() 
fib' = do l <- get 
      let l2 = sum (last2 l) 
      put (l ++ [l2]) 
      return() 
      fib' 

take 10 $ execState fib' [0, 1] 

Когда я выполняю его в REPL, ghci, функция выполняется без остановки.

Answer 1

Что вы делаете здесь более или менее эквивалентно следующему:

rfib (last:last':rest) = let new = last + last' in rfib (new:last:last':rest) 

который пытается создать числа в обратном порядке «лениво». (Приказ действительно не имеет значения, я просто сделал это в обратном порядке, чтобы избавиться от отвлекающих (++) и last2).

Но дело в том, что вы никогда не вычислите список, как скажет вам специалист по проверке типа. Например, происходит некорректно все хорошо напечатал:

res1 = (take 10 . rfib) [1,0] :: [Int] 
res2 = (take 10 . snd . rfib) [1,0] :: [Int] 
res3 = (take 10 . snd . snd . rfib) [1,0] :: [Int] 
res4 = "foo" == rfib [1,0] 

Иногда это хорошая идея не писать аннотации, вы знаете. Тогда вы увидите, был сделан вывод, что-то вроде этого:

rfib :: Num a => [a] -> b 

, которая соответствует близко к основному типу вашей Foo ':

fib' :: Num a => State [a] b 

И этот тип вы должны сделать немного подумать. В случае с rfib он сообщает, что из ниоткуда вы создаете значение любого типа, который вы хотите, здесь называется b. И это синоним «нет такого значения». Как и в случае head [] или unJust Nothing или error "Bottom", любая попытка все же вычислить это значение должна расходиться.

Вопросы различаются, когда переменная нового типа, которая появляется в результате, «защищена» конструктором типа. Тогда то, что произойдет, будет зависеть от типа, конструктор которого применяется. В его нынешнем виде он работает с Writer, но не с государством. Тем не менее, такой неожиданный тип должен заставлять думать об этом.

Answer 2

Результатом execState является значение состояния в конце вычисления. Но ваши вычисления никогда не заканчиваются: fib' звонки fib'. Хотя в вашем случае можно было бы доказать, что первые 10 элементов состояния в конечном итоге не изменяются, компилятор не может предсказать это (и не должен).

Возможно, вы захотите проверить Writer Monad, где вы можете обрабатывать письменные данные лениво.

Answer 3

return не работает, как в императивных языках. Она определяется по-разному для каждой монады, для состояния монады, она определяется как: return x = State $ \s -> (x,s)

Так что на самом деле не выйти из функции fib', но вместо этого связывает новые государственные монады к остальной части вычисления ,

EDIT:

Хотя мой первоначальный ответ, правда, он не отвечает на вопрос OP еще. В коде OP return действует как нет-op. По той причине, что код OP никогда не заканчивается, см. Другие ответы. Я до сих пор оставить свой ответ здесь, потому что я чувствую, что еще что-то важно отметить, учитывая, что return было показать излишне в образце кода в OP в

Answer 4

1. return() линия является избыточным и может быть удалена
2. (++) является почти всегда плохая идея, так как это O (N) в размере ее первого аргумента.
3. Конструируется много списков возрастающей длины, в то время как ваша цель построить один бесконечный список

Answer 5

По предложению @Joachim Брайтнеру, в одно из возможных решений с отложенной Writer монады бы:

import Control.Monad.Writer 

fib' :: Writer [Int]() 
fib' = tell [1, 1] >> go 1 1 
    where 
     go :: Int -> Int -> Writer [Int]() 
     go f1 f2 = do 
      let f3 = f1 + f2 
      tell [f3] 
      go f2 f3 

main = print $ take 10 $ execWriter fib'