0

我试图在列表中查找元素对，假设它们是列表中唯一的对，并且不超过 3 个相同的连续元素。

我有一个函数，它接收一个列表，并返回该对的第一个元素的索引（如果有的话）。如果不是，则返回 -1

searchForPairs xs = searchHelp xs ((genericLength xs) - 1)
    where searchHelp xs n
        | searchHelp xs 0 = -1              -- no pairs found
        | (xs !! n) == (xs !! (n - 1)) = n
        | otherwise = searchHelp xs n-1

由于某种原因，它返回错误：

Couldn't match expected type `Bool' with actual type `Int'
In the expression: n
In an equation for `searchHelp':
    searchHelp xs n
      | searchHelp xs 0 = - 1
      | (xs !! n) == (xs !! (n - 1)) = n
      | otherwise = searchHelp xs n - 1
In an equation for `searchForPairs':
    searchForPairs xs
      = searchHelp xs ((genericLength xs) - 1)
      where
          searchHelp xs n
            | searchHelp xs 0 = - 1
            | (xs !! n) == (xs !! (n - 1)) = n
            | otherwise = searchHelp xs n - 1

似乎它应该工作。任何想法为什么不是？

4

4 回答 4

2

我无法完全理解您想要做什么，但从代码来看，您似乎正在尝试在列表中找到两个相等的连续元素。!!您可以使用模式匹配来提取列表的前两个元素，检查它们是否相等，如果不相等，则继续搜索其余部分（包括第二个元素），而不是使用来索引列表。如果列表没有至少两个元素，则返回Nothing

searchForPairs xs = go 0 xs where
  go i (x1:xs@(x2:_)) | x1 == x2 = Just i
                      | otherwise = go (i+1) xs
  go _ _ = Nothing
于 2012-10-08T04:49:22.083 回答
2

@gereeter 已经解释了您的错误，我只想指出，如果找不到答案，您不应该返回-1。Nothing相反，如果没有答案并且Just pos答案是，您应该返回pos。这可以保护您免受多种错误的影响。

于 2012-10-08T03:51:49.380 回答
2

你有两个问题。第一个是在这一行：

        | otherwise = searchHelp xs n-1

编译器将其解释为(searchHelp xs n) - 1，而不是searchHelp xs (n-1)，如您所愿。第二个问题是你使用警卫：

        | searchHelp xs 0 = -1              -- no pairs found

由于searchHelp xs 0不是布尔表达式（您想将其用作模式），因此编译器拒绝了它。我可以看到两个简单的解决方案：

searchForPairs xs = searchHelp xs ((genericLength xs) - 1)
    where searchHelp xs n
        | n == 0 = -1              -- no pairs found
        | (xs !! n) == (xs !! (n - 1)) = n
        | otherwise = searchHelp xs (n-1)

和

searchForPairs xs = searchHelp xs ((genericLength xs) - 1)
    where
      searchHelp xs 0 = -1         -- no pairs found
      searchHelp xs n
        | (xs !! n) == (xs !! (n - 1)) = n
        | otherwise = searchHelp xs (n-1)

现在，不幸的是，虽然这可行，但效率非常低。这是因为您使用!!. 在 Haskell 中，列表是链表，因此xs !! n需要 n 步，而不是 1 步。这意味着您的函数所花费的时间是列表长度的二次方。为了纠正这个问题，你想沿着列表向前循环，使用模式匹配：

searchForPairs xs = searchHelp xs 0 where
    searchHelp (x1 : x2 : xs) pos
        | x1 == x2 = pos
        | otherwise = searchHelp (x2 : xs) (pos + 1)
    searchHelp _ _ = -1
于 2012-10-07T23:34:06.747 回答
1

对于它的价值，这里有一个你正在尝试做的有点惯用（和无点）的实现：

searchPairs :: Eq a => [a] -> Maybe Int
searchPairs = interpret . span (uncurry (/=)) . (zip <*> tail)
    where
    interpret (flag, res) = if null flag then Nothing else Just $ length res

说明：zip <*> tail创建连续元素对的列表（使用阅读器应用类型类）。uncurry (/=)测试这样的一对是否由相同的元素组成。最后，interpret将结果转换为Maybe Int类型值。

于 2014-07-22T10:13:59.203 回答