haskell - Type error when asigning tuple in do notation in haskell

Question

This is the haskell code I have:

myFold:: ([a] -> (b, [a])) -> [a] -> [b]
myFold fn []  = []
myFold fn lst = do
    (ast, newLst) <- (fn lst)
    myFold fn newLst ++ [ast]

I think everybody who knows haskell will get what I want to do. However this code is wrong and I really don't get why. The compiler complains that the types don't match in the line (ast, newLst) <- (fn lst) and I cannot see what's wrong.. Can somebody point me to how the syntax must be? Also I am pretty sure that there are better ways to do this so please feel free to provide alternatives.

标签： haskell

Answer 1

Short answer: Stop using do notation. It does not do what you think it does.

Long answer:

do-notation is being misused here. I won't do a full monad tutorial here, but I'll show you what you should have done, line by line.

Firstly, the line myFold fn lst = do is wrong, because you shouldn't be using do-notation, so let's remove it:

myFold fn lst =

Secondly, the line (ast, newLst) <- (fn lst) is misusing a construct in do-notation, namely the arrow. What you actually want is a plain old let-statement, so let's replace that, noting that we also need an accompanying in later.

    let (ast, newLst) = fn lst

Thirdly, you need an in when you express the value you want to return:

    in myFold fn newLst ++ [ast]

So, all in all:

myFold fn lst =
    let (ast, newLst) = fn lst
    in myFold fn newLst ++ [ast]

If you want to find out how to properly use do-notation, provided that you understand Monads, there are plenty of tutorials available online. I will not explain this here because this is completely outside the scope of the core issue in this code.