Haskell Infinite Type

Question

I am trying to get the code below. This is a state machine in which I go into the function-as-next-state. The function is called with r and returns a list of results + the next state of the function-as-next. Keep calling until the list ends and return the concatenation of the results. Monad is a monad of errors, which allows me to give an error if necessary.

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

Error:

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

I have seen an error with an infinite type before, and I understand that you need to wrap the type around it with newtype . But I can’t figure out how to do this.

Can anyone point out 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 fr rest <- fsm f' rs return $ xs ++ rest 

You are correct that you need to use data or newtype anytime a recursive type is required.

In response to your comment here, you can implement your dup function:

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

... or you can split it into two separate definitions if you want.

Please note: if you are not sure what a type signature is, just enable the NoMonomorphismRestriction extension and the compiler will not complain and will correctly output the top level type for you.