Haskell笛卡尔积，带有过滤器的Monad

Question

我希望这个问题足够简单，但在我的Haskell编程经验中，我却无法解决它。我想获得一个列表的笛卡尔积，但是我希望过滤掉相同的项，而不是在计算之后再进行过滤。

这段代码会给我笛卡尔积 - 看起来只需要加上一个过滤器...

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

我读到过return ()在do记法中基本上是一个无操作的操作，但是这段代码无法编译。（元组被搞混了吗）

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: [()]

我尝试了一些其他方法，比如来自Haskell维基的if'函数。 我也尝试了when但没有成功。 当过滤器是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)

我想这些错误信息可能会引导我找到问题，但我还不熟练地翻译它们。

很可能有一个更高级的函数可以更简单地处理这个问题（filterM？），如果您知道使用方法，我会很高兴听到它，但我仍然想知道如何解决上面pf函数中的问题。

谢谢

- user49011

---

你不妨使用列表推导式：[(a, b) | a <- as, b <- bs, a == b]。这段代码可以帮你筛选出在列表 as 和列表 bs 中相等的元素对，并将它们以元组的形式存储在列表中。 - daylily

感谢您提供“更简单的方式”。 - user49011

这根本不是无操作。在列表单子中，return () == [()]。你读到的可能是特定于IO单子的典型用法。例如，putStrLn :: String -> IO ()，它创建了一个IO操作，当执行时，会将一些字符写入标准输出并产生值()。由于实际上没有人关心执行类型为IO()的操作所产生的值，因此return ()在创建的操作中是无操作，它不进行任何输入或输出；它只产生预期和所需的值()。 - chepner

我对chepner的看法不同：即使在列表单子中，“return ()”也可以被合理地认为是无操作。但是，你分支语句的另一半不是无操作，实际上返回了某个有趣类型的值。无操作不是一个合适的替代品；它不会返回那个有趣类型的值（尤其是在列表单子中，甚至不会返回没有那个有趣类型的值——试着理解这个双重否定！）。 - Daniel Wagner

return()在某种意义上是一个无操作，因为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) }。你可以将其放在do块的任何一行，除了最后一行，它都不会改变任何东西。这对于_任何_单子都是正确的。(cc @chepner) - Will Ness

Answer 1

尝试：

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)

我最近才开始学习Haskell，所以可能有些错误。在这个上下文中，return (a, b)仅仅是表达式[(a, b)]的另一种写法（这很自然，因为对于单子[]，你需要一个输出类型为[t]的函数）。因此，你需要提供相同的类型，即空列表[]。

另一方面，当你写return ()时，实际上是[()]，其类型是[()]，与例如类型[(Int, Int)]不同。

- j1-lee

---

我学到了一些新知识。我不知道return (a,b)等同于[(a,b)]。我曾经认为必须使用return将一个值提升到输出上下文中（有时我太过字面理解）。谢谢。 - user49011

其他的例子是，对于Maybe类型，可以使用return a = Just a；对于Either类型，可以使用return a = Right a。我们还可以观察到Applicative f => Monad f，这意味着return = pure。 - pedrofurla

它确实如此。do符号会被展开为as >>= \a -> bs >>= \b -> if a == b then [] else return (a, b)。return必须生成一个列表，以使条件表达式能够通过类型检查。正是>>=的定义导致了该表达式（每次使用不同的a和b值）被多次求值。对于列表来说，这意味着将元组(a, b)提升到列表[(a, b)]中。直观地说，return必须产生正确类型的最简单的非平凡值。 - chepner

你可能认为 "[] 比 [(a, b)] 更简单", 但在单子定律的背景下，[] 并不是非平凡的。 - chepner

@chepner，你不能仅使用[]类型的单子函数来创建[]数据。你需要使用MonadPlus（或在其中一个操作中使用[]数据字面量）。 - Will Ness

IOW单子律不知道mzero的存在，而[]数据是它的一部分。我认为它们也不知道fail "" :: [()]的存在。 - Will Ness

Answer 2

您也可以使用Control.Monad.guard代替直接使用[]。

import Control.Monad (guard)

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

你可以把它看作是一种 do 符号版本的列表推导式 [(a, b) | a <- as, b <- bs, a /= b]。

- snak

---

请注意，guard True == [()] 和 guard False == []。由于列表单子的定义方式，仅空列表和非空列表之间的差异才有意义，而不是 guard 返回的列表的实际内容。 - chepner

由于 Haskell 是惰性的，因此 \_ -> return (a, b) 只有在它绑定到的列表包含值时才会被调用。[()] 可以提供一个参数（被忽略），但 [] 不行。换句话说，guard x >> return (a, b) == guard x >>= \_ -> return (a, b)。 - chepner

@chepner - 我非常感谢您在这里的各种帖子中发表的所有评论。它们指出了我知识上的很大漏洞，并为我提供了许多探索的途径。 - user49011

Answer 3

你可以修复你的

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

通过将其更改为

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

如果m是[]类型，那么这将得到我们。

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

现在它确实通过了类型检查器，但我们在所需的类型周围创建了一个额外的[]层：

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

所以这几乎就是我们想要的，除了一些额外的[]作为保险措施。如果我们能让它们消失该多好啊！

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

正如您在上面所看到的，我们通过将pf3的输出传递给concat，获得了最终期望的值。但是concat就像[]-类型单子的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

被定义为

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

因此，我们上面所写的内容融合在一起，形成如下：

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)
         }

无论您喜欢最后两个中的哪一个。前两个是您通常手写的内容，而最后一个对应于在第三个do行中使用reject(a==b)，并定义如下：

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

对于[]类型的单子，mzero = [] :: [] a（当然，return x = [x] :: [] a）。

恰好reject b = guard (not b)，使用内置的guard函数。

---

一个旁注：

return () 是一种无操作，因为

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) }

你可以将它放在 do 块的任何一行，除了最后一行，它不会改变任何事情。这对于 任何 Monad 都是正确的。

- Will Ness