CODEWITHSUNDEEP
haskellstate
Jay
Jay

Reputation: 1101

State Monad never ends

Could somone please tell me why does this piece of code which uses the State monad never end?

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

take 10 $ execState fib' [0, 1]

When I execute it in the ghci REPL, the function executes without stopping.

Upvotes: 2

Views: 276

Answers (5)

DJG
DJG

Reputation: 6563

return does not work like it does in imperative languaues. It is defined differently for each monad, for the state monad, it is defined as: return x = State $ \s -> (x,s)

So it doesn't actually break out of the fib' function, but instead binds a new State monad to the rest of the computation.

EDIT:

While my original answer is true, it does not answer the OP's question. In the OP's code, return acts as a no-op. For the reason why the OP's code never terminates, see other answers. I am still leaving my answer here because I feel it is still something important to point out, given that return did show up unnecessarily in the OP's code sample

Upvotes: 4

Ingo
Ingo

Reputation: 36339

What you are doing here is more or less equivalent to the following:

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

which attempts to create the numbers in reverse order "lazily". (The order doesn't really matter, I just did it in reverse to get rid of the distracting (++) and last2).

But the point is, you never compute a list, as the type checker will tell you. For example, the follwoing are all well typed:

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]

Sometimes it is a good idea to not write annotations, you know. Then you would see that something like this was inferred:

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

which corresponds closely to the principal type of your foo':

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

And this type should you make think a bit. It the case of rfib it tells that out of nowhere you create a value of any type you want, here called b. And this is synonymous for "there is no such value". Like in head [] or unJust Nothing or error "Bottom", any attempt to nevertheless compute that value must diverge.

Matters are different when the fresh type variable that appears in the result is "protected" by a type constructor. Then what happens will depend on the type, whose constructor is applied. As it stands, it works with Writer, but not with State. Still, such an unexpected type should make one think the case over.

Upvotes: 1

bheklilr
bheklilr

Reputation: 54078

At @Joachim Breitner's suggestion, a possible solution using the lazy Writer monad would be:

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'

Upvotes: 1

nponeccop
nponeccop

Reputation: 13677

  1. return () line is redundant and can be removed
  2. (++) is almost always a bad idea as it's O(N) in the size of its first argument.
  3. You construct many lists of increasing length, while your goal is construct a single infinite list

Upvotes: 4

Joachim Breitner
Joachim Breitner

Reputation: 25782

The result of execState is the value of the state at the end of the computation. But your computation never ends: fib' calls fib'. While in your case it would be possible to prove that the first 10 elements of the state eventually do not change, the compiler is not able to predict that (nor should it).

You might want to check out the Writer Monad, where you can process the written data lazily.

Upvotes: 8

Related Questions