Haskell Cartesian Product, Monad with filter

Question

This has to be dead simple and I'm unhappy I can't figure it out at this point in my Haskell experience. I want a cartesian product of a list with itself, but I want to filter out identical items. I don't want a post filter.

This gets me the CP - seemingly set up to simply add a filter...

p as bs = do
            a <- as
            b <- bs
            return (a,b)

p [1,2,3] [1,2,3]
[(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)]

I have read that return () is basically a noop in do notation - but this doesn't compile. (Are the tuples being mixed up)

pf as bs = do
            a <- as
            b <- bs
            if a == b then return () else return (a,b)

* Couldn't match type `()' with `(a, a)'
      Expected type: [(a, a)]
        Actual type: [()]

I have tried a few other things, like the if' function from the Haskell wiki. I also tried when without success. When the filter is when

when (a /= b) return (a,b)

* Couldn't match type `m0 (a, a)' with `()'
      Expected type: (a, a) -> ()
        Actual type: (a, a) -> m0 (a, a)

I suppose these error messages are leading me by the nose to the issue but I am not adept at translating most of them yet.

There is very possibly a higher level function that might handle this in a more straight forward way (filterM ?), and I'll be happy to hear about its usage, but I still want to know how to solve this issue in the pf function above.

Thanks

user_11450820 · Answer

Try:

main = print $ p [1,2,3] [1,2,3] -- [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

p as bs =
  do
    a <- as
    b <- bs
    if a == b then [] else return (a, b)

I've learned Haskell a bit only recently, so I may be wrong. In this context, return (a, b) is nothing more than the expression [(a, b)] (which is natural, since for monad [] you need a function with the output of type [t]). So you need to provide the same type, i.e., the empty list [].

On the other hand when you write return () it actually is [()], whose type is [()], which is not the same as, say, the type [(Int, Int)].

user_1378868 · Answer

You can also use Control.Monad.guard instead of using [] directly.

import Control.Monad (guard)

p as bs =
  do
    a <- as
    b <- bs
    guard $ a /= b
    return (a, b)

You can think this as a do-notation version of the list-comprehension [(a, b) | a <- as, b <- bs, a /= b].

user_849891 · Answer

You can fix your

pf as bs = do
             a <- as
             b <- bs
             if a == b then return () else return  (a,b)

by changing it to

pf2 :: (Monad m, Eq t) => m t -> m t -> m [(t, t)]
pf2 as bs = do
             a <- as
             b <- bs
             if a == b then return [] else return [(a,b)]

In case the m is []-type, this gets us

pf3 :: (Eq t) => [t] -> [t] -> [ [(t, t)] ]
pf3 as bs = do
             a <- as
             b <- bs
             if a == b then return [] else return [(a,b)]

so it does pass the type-checker now, but we've created an extra layer of [] around our desired type:

> pf3 [1,2,3] [1,2,3] :: [ [(Int,Int)] ]
[[],[(1,2)],[(1,3)], [(2,1)],[],[(2,3)], [(3,1)],[(3,2)],[]]

So this is almost what we wanted, except for some extra []s thrown around for good measure. If only we could make them disappear,

> concat it
[    (1,2),  (1,3),   (2,1),     (2,3),   (3,1),  (3,2)    ]

we'd get what we really wanted as the end result.

As you can see above we did get the final desired value, by passing the output of pf3 through concat. But concat is []-type-monad's join:

> :t concat :: [] ([] a) -> [] a
concat ::       [] ([] a) -> [] a   :: [[a]] -> [a]

> :t join ::   [] ([] a) -> [] a
join ::         [] ([] a) -> [] a   :: [[a]] -> [a]

> :t join
join :: Monad m => m (m a) -> m a

which is defined as

join xs = do                    = do
           { x <- xs               { x <- xs
           ; x                     ; y <- x
           }                       ; return y
                                   }

and thus what we wrote above fuses together as

pf4 as bs = join $ do
                     a <- as
                     b <- bs
                     if a == b then return [] else return [(a,b)]
    = do {
           x <- do { a <- as
                   ; b <- bs
                   ; if a == b then return [] else return [(a,b)] }
         ; x 
         }
    = do {           a <- as
                   ; b <- bs
         ; x <-      if a == b then return [] else return [(a,b)]
         ; x
         }
    = do { a <- as
         ; b <- bs
         ; let { x = if a == b then  []  else  [(a,b)]  }
         ; x
         }
    = do { a <- as
         ; b <- bs
         ;      if a == b then  []  else  [(a,b)]
         }
    = do { a <- as
         ; b <- bs
         ;      if a == b then  []  else  [()]
         ; return (a,b)
         }

whichever of the last two you prefer. The first of the two is what you'd normally write out by hand, and the last corresponds to using reject (a==b) as the third do line, with the definition

reject :: MonadPlus m => Bool -> m ()
reject True  = mzero         -- mzero :: MonadPlus m => m a
reject False = return ()     -- () to be ignored

where for the []-type monad, mzero = [] :: [] a (and of course, return x = [x] :: [] a).

It so happens that reject b = guard (not b), with the built-in guard.

A side remark:

return () is a no-op in the sense that

do {             a <- as ; b <- bs ; return (a,b) } ==
do { return () ; a <- as ; b <- bs ; return (a,b) } ==
do { a <- as ; return () ; b <- bs ; return (a,b) } ==
do { a <- as ; b <- bs ; return () ; return (a,b) }

You can put it on any line of the do block except the last one and it won't change a thing. This is true for any monad.

Haskell Cartesian Product, Monad with filter

3 Answers