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.

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`). — chi, Nov 16 '21 at 12:35
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? — daikonradish, Nov 17 '21 at 02:56
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? — chi, Nov 17 '21 at 12:05
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". — chi, Nov 17 '21 at 12:11
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.) — daikonradish, Nov 17 '21 at 17:09
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?". — chi, Nov 17 '21 at 18:01
@daikonradish see https://stackoverflow.com/tags/do-notation/info: "... the type of the final action in the do block is the type of the overall do block" — Will Ness, Nov 18 '21 at 13:24
see also: [Using return vs. not using return in the list monad](https://stackoverflow.com/q/11323300/849891). — Will Ness, Nov 18 '21 at 13:33

4castle · Answer 1 · 2021-11-16T18:04:18.420

9

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)

edited Nov 16 '21 at 18:04

answered Nov 16 '21 at 12:34

4castle

32,613
11
69
106

thanks! I learned something new from the `guard` abstraction. It does seem like evil imperative programming though hehe – daikonradish Nov 17 '21 at 02:53

score 8 · Answer 2 · answered Nov 16 '21 at 11:46

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 []

Do-notation and the list monad

2 Answers2