检查重复项列表时 nub 不编译

Question

正在做一个受数独启发的作业，我需要实现一个函数来检查 Block Cell 中是否没有重复元素（以检查它是否是拼图的有效解决方案）。

okBlock :: Block Cell -> Bool
okBlock b = okList $ filter (/= Nothing) b
 where
  okList :: [a]-> Bool
  okList list
   | (length list) == (length (nub list)) = True
   | otherwise                            = False

Block a = [a]
Cell = [Maybe Int]

Haskell 抱怨说 No instance for (Eq a) arising from a use of "==" Possible fix: add (Eq a) to the context of the type signature for okList...

在类型签名中添加 Eq a 没有帮助。我已经在终端中尝试了该功能，它适用于列表和列表列表（即我在函数中输入的类型）。

我在这里错过了什么？

Answer 1

如果有检查两个值是否重复的方法，那么您只能过滤掉重复项。如果我们查看 nub 的类型签名，我们会看到：

nub :: Eq a => [a] -> [a]

所以这意味着为了过滤掉 a 列表中的重复项，我们需要 a 成为 Eq class 的实例。因此，我们可以简单地在函数的签名中进一步转发类型约束：

okBlock :: Block Cell -> Bool
okBlock b = okList $ filter (/= Nothing) b
 where
  okList :: <b>Eq => </b>[a] -> Bool
  okList list
   | (length list) == (length (nub list)) = True
   | otherwise                            = False

我们不需要指定Cell是Eq的一个实例，因为：

Int 是 Eq 的实例；
如果a是Eq的实例，Maybe a也是，所以Maybe Int是Eq的实例；和
如果a是Eq的实例，[a]也是，所以[Maybe Int]是Eq的实例。

也就是说我们可以对代码进行一些语法改进：

如果您只是 return 守卫 True 和 False 以及
您可以使用 eta 缩减 并省略 okBlock 中的 b。
函数应用程序不需要括号（除非将结果直接提供给另一个非中缀函数）。

这给了我们：

okBlock :: Block Cell -> Bool
okBlock = okList . filter (/= Nothing)
  where
    okList :: Eq => [a] -> Bool
    okList list = length list == length (nub list)

最后要注意的是，通常您 不必指定类型签名。在这种情况下，Haskell 将致力于获取最通用的类型签名。所以你可以这样写：

okBlock = okList . filter (/= Nothing)
  where
    okList list = length list == length (nub list)

现在 okBlock 将具有类型：

Prelude Data.List> :t okBlock
okBlock :: Eq a => [Maybe a] -> Bool

Answer 2

三点太大了，评论不出来。

`nub` 太慢了

nub 需要 O(n^2) 时间来处理长度为 n 的列表。除非您知道列表很短，否则这是用于从列表中删除重复项的 错误函数 。添加更多有关您正在处理的事物类型的信息，可以实现更有效的微调。最简单的，也可能是最通用的方法，并不是绝对糟糕的方法是使用 Ord 约束：

import qualified Data.Set as S

nubOrd :: Ord a => [a] -> [a]
nubOrd = go S.empty where
  go _seen [] = []
  go seen (a : as)
    | a `S.member` seen = go seen as
    | otherwise = go (S.insert a seen) as

`length`浪费

假设我写

sameLength :: [a] -> [b] -> Bool
sameLength xs ys = length xs == length ys

（使用您所做的方法）。现在假设我计算

sameLength [1..16] [1..2^100]

这需要多长时间？计算 length [1..16] 将花费纳秒。使用当前的硬件计算 length [1..2^100] 可能需要数十亿年。哎呀。什么是正确的方法？模式匹配！

sameLength [] [] = True
sameLength (_ : xs) (_ : ys) = sameLength xs ys
sameLength _ _ = False

摩擦不是解决这个问题的正确方法

假设我问 noDuplicates (1 : [1,2..])。显然，有一个副本，就在开头。但是如果我使用 sameLength 和 nub 来检查，我将 永远不会得到答案 。它将继续构建 nubbed 列表并将其与原始列表进行比较，直到 seen 变得如此之大以至于耗尽计算机的内存。你怎么能解决这个问题？通过直接计算你需要什么：

noDuplicates = go S.empty where
  go _seen [] = True
  go seen (x : xs)
    | x `S.member` seen = False
    | otherwise = go (S.insert x seen) xs

现在程序会在看到第二个时断定存在重复项 1。

检查重复项列表时 nub 不编译

nub not compiling when checking a list for duplicates

haskell

list

sudoku

typeclass

`nub` 太慢了

`length`浪费

摩擦不是解决这个问题的正确方法

检查重复项列表时 nub 不编译

nub not compiling when checking a list for duplicates

haskell

list

sudoku

typeclass

nub 太慢了

length浪费

摩擦不是解决这个问题的正确方法

`nub` 太慢了

`length`浪费