Haskell Infinite Type

Question

I'm trying to get the code below working. It's a finite state machine where I pass in a function-as-next-state. The function is called with r and returns a list of results + the next function-as-next state. Keep on calling until the list runs out, and return the concatenation of the results. The monad is an error monad to allow me to throw an error if needed.

fsm f []     = return []
fsm f (r:rs) = do
    (xs, f') <- f r
    rest     <- fsm f' rs
    return $ xs ++ rest

The error is:

Occurs check: cannot construct the infinite type: t1 = t0 -> m0 ([a0], t1)
In the first argument of `fsm', namely f'

I've seen the infinite type error before and I understand the way around it is to wrap a type with a newtype. But I cannot figure out how to get this done.

Can someone point out the insight?

Answer 1

I think this is what you want:

newtype F m = F { unF :: String -> m ([String], F m) }

fsm :: (Monad m) => F m -> [String] -> m [String]
fsm f []     = return []
fsm f (r:rs) = do
    (xs, f') <- unF f r
    rest     <- fsm f' rs
    return $ xs ++ rest

You are right that you need to use a data or newtype any time you want a recursive type.

In reply to your comment, here's how you would implement your dup function:

dup :: (Monad m) => F m
dup = F dup' where dup' xs = return ([xs, xs], F dup')

... or you could split it up into two separate definitions if you prefer.

Note that if you are not sure what the type signature should be, just enable the NoMonomorphismRestriction extension and the compiler will not complain and correctly infer the top-level type for you.