Adding a Writer Monad inside foldl function Haskell

Question

I implemented a function that searched for a specific node inside a tree. Here's the function and it works:

searchTree :: String -> Tree String -> Bool
searchTree value tree =
    foldl (\acc x -> if value `elem` x then True else acc) False (levels tree)

Then, I'm trying to implement the same function, but this time, I want to add a Writer Monad. This one doesn't work and the compiler says "Couldn't match expected type 'Writer [String] Bool' with actual type 'Bool' " -> The error is in the 4th line, in the instruction 'return True'.

searchTree :: String -> Tree String -> Writer [String] Bool
searchTree value tree =
    foldl (\acc x -> if value `elem` x then do
        tell ["My logger message "]
        return True else acc) return False (levels tree)

Thanks in advance.

Answer 1

You are missing parenthesis around return False:

searchTree :: String -> Tree String -> Writer [String] Bool
searchTree value tree =
    foldl (\acc x -> if value `elem` x then do
        tell ["My logger message "]
        return True else acc) (return False) (levels tree)

Tip: To make such bugs easier to find, I always remove my hard-coded type signatures, because the problem may be that I'm misunderstanding types. In this case removing the type signature changed the error to:

Couldn't match expected type `Bool' with actual type `m0 a0' 
Expected type: a0 -> Bool 
Actual type: a0 -> m0 a0 
In the second argument of `foldl', namely `return'
In the expression:
    foldl (\acc x -> if value `elem` x then do
        tell ["My logger message "]
        return True else acc) (return False) (levels tree)

Answer 2

Note that in cases like these, you (usually) really do want to use foldr instead.

searchTree :: String -> Tree String -> Writer [String] Bool
searchTree value tree =
    foldr (\x continue -> if value `elem` x then do
        tell ["My logger message "]
        return True else continue) (return False) (levels tree)

The reasons being, this won't inspect the entire list, but stop at the first elem value x, in most cases (the writer monad included) associating (>>=) to the right is more efficient than associating to the left, and foldr is compatible with GHC's list fusion whereas foldl is not.