Haskell -- Unexpected expected type

Question

I'm trying to write a function in Haskell that will pop some items that have been serialized to a list of strings. (This list represents the lines of a text file -- one line is not necessarily one item)

The function is called with another function as a parameter. This function will pop a single item off, and return a tuple containing that item and the remainder of the text. The function is supposed to recursively perform this operation n times, each time adding the result a list. It returns this list along with the remainder of the text, to be used for further parsing.

popN :: Integer -> [String] -> ([String]-> (a, [String])) -> ([a], [String])
popN n txt fun  | n == 0 = ([], txt)
                | n /= 0 = do
                    let (tp, newtxt) = fun txt
                    let newnum = n - 1
                    let (rest, after) = popN newnum newtxt fun
                    return (tp : rest, after)

When I attempt to compile this code, I get the following error:

Couldn't match the expected type '[String]' with actual type '([a], [String])'
In the first argument  of 'return', namely '(tp : rest, after)'

The actual type, ([a], [String]) is the type I would expect. What I don't understand, however, is why [String] is the expected type. Could someone explain to me why GHC expects this function to return a [String]?

Thanks in advance for any help.

Answer 1

return takes a value of type t and produces a value of type m t where m is some monad. The result of your function is the result of applying return to an argument. So which type must that argument have if the result is to be of type ([a], String)? Well, the only way that return x could produce a value of type ([a], String) would be if x had type [String] and m was the type constructor (,) [a] (not taking into account, at that point, that presumably no such instance exists in the prelude). Therefore the type checker expects the argument to be a [String].

Answer 2

In this case, you cannot use monads because the tuple that you are returning is not a monad. You can use simple recursion like so:

popN :: Integer -> [String] -> ([String]-> (a, [String])) -> ([a], [String])
popN 0 txt _    = ([], txt)
popN n []  _    = ([], [])
popN n txt fun  = (tp:rest, newtxt1)
    where
        (tp,   newtxt ) = fun txt
        (rest, newtxt1) = popN (n-1) newtxt fun

Answer 3

do is for monadic functions, but yours is pure:

popN :: Integer -> [String] -> ([String]-> (a, [String])) -> ([a], [String])
popN 0 txt _ = ([], txt)
popN n txt fun = (a:as, txt'') where
    (a, txt') = fun txt
    (as, txt'') = popN (n-1) txt' fun

It does appear that txt is acting as state that is threaded through the function, and could be hidden by using the State monad.

type S = State [String]

popN :: Integer -> S a -> S [a]
popN 0 _ = return []
popN n m = do
    a <- m
    as <- popN (n-1) m
    return (a:as)

But this is basically replicateM (if you can deal with Int instead of Integer).