Do-notation and the list monad

Question

I am learning Haskell.

I am trying to find elements of a list as which sum to elements of a list bs, returning the elements as a tuple:

findSum2 :: [Int] -> [Int] -> [(Int,Int,Int)]
findSum2 as bs = [(a, a', b) | a <- as, a' <- as, b <- bs, a + a' == b]

The code works. But in order to learn Haskell, I'm trying to rewrite it as do-notation:

findSum2 :: [Int] -> [Int] -> [(Int,Int,Int)]
findSum2 as bs = do
  a  <- as
  a' <- as 
  b  <- bs
  if a + a' == b then return (a, a', b) 
                 else return ()

The type-checker then complains at me:

   • Couldn't match type ‘()’ with ‘(Int, Int, Int)’
      Expected type: [(Int, Int, Int)]
        Actual type: [()]

In all fairness, I knew it would. But since I can't skip the else clause in Haskell, what should I put in the return statement in the else clause?

Thanks.

Xylem

In the list monad, return (a,a',b) means the singleton list [(a,a',b)] which signals "I found a triple, (a,a',b), add it to the result list". Similarly, return () means [()], i.e. "I found a triple, (), add it to the result list", triggering a type error since that's no triple. To signal, "I found no triple this time" use the empty list [] (without any return). – Referendum

ah. I'd tried return [], but clearly that was wrong too. I think I'm still struggling with do-notation. How did you get to a place where you could recognize when to return automatically? – Xylem

You have to "think with types" -- in Haskell that's one of the most important skills. You are working with a monad (the list monad []), so you need to keep in mind what's just a random value and what's a monadic action. return is not a magic primitive, but a function that turns any value x into a boring monadic action that only has that value inside (the singleton list [x], in this monad). If you have x = [], do you really need to wrap it inside a list again? – Referendum

Compare the list comprehensions [ a | a <- [1,2,3] ] and [ a | a <- [[1,2,3]] ]. In the former, a ranges over 1,2,3, while in the latter a has only one value, the list [1,2,3]. That's because we added an extra [.....]. We probably didn't want that, and that's the same issue that you found between [] and return [] (i.e., [[]]). In the list monad, use return only what you want to signal "one value found", not "no values found here". – Referendum

Okay, so I made another discovery today, which is that RETURN ONLY WORKS WITH TYPES. The hint was useful, and helped me go down a path I'd already been suspecting but only manage to confirm today. But to confirm: when you look at a function and it says return inside a do-block, do you automatically also stare at the type signature to understand which return is being called? (That's what I'm starting to do now.) – Xylem

I'd say so. When defining, say, action :: M Int as action = do .. ; .. ; .. ; lastEntry we must have lastEntry :: M Int. Often, lastEntry is return expression which turns expression :: Int into an M Int value. Another common lastEntry is a function call foo x y where foo :: ... -> ... -> M Int. Ending the block with foo x y is equivalent to ending with z <- foo x y ; return z (the former is the preferred form, the latter is a kind of antipattern). In any case, yes, when I use return I always think "which monad am I using here?". – Referendum

@Xylem see stackoverflow.com/tags/do-notation/info: "... the type of the final action in the do block is the type of the overall do block" – Sequin

see also: Using return vs. not using return in the list monad. – Sequin

Answer 1

You must return something of the correct type in the else clause. It could be the empty list [], or one of the abstracted values like mzero or empty.

Or you could remove the if expression and use the guard function.

import Control.Monad (guard)

findSum2 :: [Int] -> [Int] -> [(Int,Int,Int)]
findSum2 as bs = do
  a  <- as
  a' <- as 
  b  <- bs
  guard (a + a' == b)
  return (a, a', b)

With this implementation you could now also generalize your function signature to:

findSum2 :: MonadPlus m => m Int -> m Int -> m (Int, Int, Int)

Bushelman

thanks! I learned something new from the guard abstraction. It does seem like evil imperative programming though hehe – Xylem

Answer 2

You can not return the unit (()), since that means that the return (a, a', b) and the return () have different types: the first one is [(Int, Int, Int)], whereas the latter is [()].

What you can do is use an empty list in case the guard fails, so:

findSum2 :: [Int] -> [Int] -> [(Int,Int,Int)]
findSum2 as bs = do
  a  <- as
  a' <- as 
  b  <- bs
  if a + a' == b then return (a, a', b) else []

Harpole