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

Question

这必须非常简单，我很不高兴，根据我的 Haskell 经验，我目前无法弄清楚。我想要一个列表的笛卡尔积，但我想过滤掉相同的项目。我不想要 post 过滤器。

这让我得到了 CP - 似乎设置为简单地添加一个过滤器...

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 符号中的一个 noop - 但这不会编译。（元组是否混淆）

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 wiki 中的 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 函数中的问题。

谢谢

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)]（这很自然，因为对于 monad [] 你需要一个输出类型为 [t] 的函数）。所以你需要提供相同的类型，即空列表 [].

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

Answer 2

您也可以使用 Control.Monad.guard 而不是直接使用 []。

import Control.Monad (guard)

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

您可以将其视为列表理解 [(a, b) | a <- as, b <- bs, a /= b].

的 do 表示法版本

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

所以它现在确实通过了 type-checker，但是我们在我们想要的类型周围创建了一个额外的 [] 层：

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

所以这几乎就是我们想要的，除了一些额外的 []s 为了更好地衡量。如果我们能让它们消失就好了，

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

我们会得到我们真正想要的最终结果。

正如您在上面看到的那样，我们通过将 pf3 的输出传递给 concat，确实获得了最终所需的值。但是concat是[]-type-monad的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)
         }

你喜欢最后两个中的哪个。两者中的第一个是您通常手写的内容，最后一个对应于使用 reject (a==b) 作为第三行 do，定义为

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

对于 [] 类型的 monad，mzero = [] :: [] a（当然还有 return x = [x] :: [] a）。

刚好reject b = guard (not b)，与built-in guard.

旁注：

return () 是 no-op 在某种意义上

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 块的任何一行，除了最后一行，它不会改变任何东西。 any monad 也是如此。

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

Haskell Cartesian Product, Monad with filter

monads

haskell

filter