haskell - 是否可以扩展 elem 以支持 a -> [[a]] -> Bool？

Question

我有一个多联骨牌问题，需要将多联骨牌放在板上。我正在使用以下类型来支持这一点。

type Block = (Int, Int)
type Polyomino = [Block]
type Board = [Polyomino]

我的解决方案的一部分是一个函数，用于检查是否有任何多联骨牌 block 已放置在棋盘中。

unPlaced :: Polyomino -> Int -> Int -> Board -> Bool
unPlaced _ _ _ [] = True
unPlaced ((a, b):cs) x y b = --check if in Board

(x 和 y 是当前多骨牌的偏移量)

我知道我可以使用elem来检查板上的每个多联骨牌，就像这样

unPlaced ((a, b):cs) x y b:bs = if (((a+x),(b+y)) `elem` b) 
then False
else unPlaced ((a, b):cs) x y bs

但我不确定如何完成此解决方案，因为在检查了电路板的每个元素后我无法“刷新”电路板。

我相信函数 a -> [[a]] -> Bool 将允许我完成此操作，因此我们将不胜感激!

Answer 1

您可以通过组合其他函数轻松获得具有该签名的函数，但是有不止一种方法可以实现这一点，并且具有不同的行为，因此哪一种对您有用取决于您希望它具有的行为。

一种方法是提升elem。如果您查看 elem 的类型，它具有以下类型:

Prelude> :t elem
elem :: (Eq a, Foldable t) => a -> t a -> Bool

因此，您可以做的一件事是将 a 类型的第一个值提升为 Functor，如下所示:

pelem :: (Applicative f, Eq (f a), Foldable t) => a -> t (f a) -> Bool
pelem = elem . pure

不过，它可能不会做你想做的事:

*Q49002862> pelem "foo" [["foo", "bar"],["baz"]]
False
*Q49002862> pelem "baz" [["foo", "bar"],["baz"]]
True

请注意，它将 "foo" 提升为 ["foo"]，并将 "baz" 提升为 ["baz"]，这样只有最后一个查询返回 True。

这可能不是您想要的，因此，您也可以从 Control.Monad 引入 join 并定义 jelem，如下所示:

jelem :: (Foldable t, Eq a, Monad t) => a -> t (t a) -> Bool
jelem x = elem x . join

只要在展平(连接)可折叠容器中仅找到一个元素，就会返回True:

*Q49002862> jelem "foo" [["foo", "bar"],["baz"]]
True
*Q49002862> jelem "baz" [["foo", "bar"],["baz"]]
True
*Q49002862> jelem "qux" [["foo", "bar"],["baz"]]
False

我确信人们可以想出一种限制较少的后者的实现(例如不要求 t 是 Monad)，但这就是我可以在短时间内想到。

需要明确的是，pelem 和 jelem 这两个词是我现在编造的。它们没有任何意义 - 我只是分别取出 pure 和 join 的第一个字母，并将它们放在 elem 前面。