Haskell 中最长的公共前缀

Question

我试图根据文件的最长公共前缀 cpfx 来匹配文件，并且对 haskell 有点陌生。我正在尝试获取列表列表并简单地返回它们共享的前缀。例如：

cpfx ["obscure","obscures","obscured","obscuring"] --> "obscur"

cpfx ["abc", "ab", "abcd"] --> "ab"

我正在尝试使用几个辅助方法，如下所示：

cpfx :: [[Char]] -> [Char]
cpfx [] = [] -- nothing, duh
cpfx (x:[]) = x -- only one thing to test, return it
cpfx (x:t) = cpfx' (x:t) 0 -- otherwise, need to test

cpfx' (x:[]) _ = []
cpfx' (x:t) n
-- call ifMatch to see if every  list matches at that location, then check the next one
      | ifMatch (x:t) n = x!!n + cpfx' x (n+1)
      | otherwise = []

-- ifMatch means if all words match at that location in the list
ifMatch (x:[]) _ = True
ifMatch (x:xs:[]) n = x!!n == xs!!n
ifMatch (x:xs:t) n
      | x!!n == x!!n = ifMatch xs n
      | otherwise = False

但我收到错误： Occurs check: cannot construct the infinite type: a0 = [a0]

我猜这与ifMatch (x:t) n = x!!n + cpfx' x (n+1)线路有关。

我能做些什么来补救这个案子？

Answer 1

如何解决这些错误

注意：虽然我将向您展示如何理解和解决这些错误，但我还在下面提供了一个更优雅的版本（至少从我的角度来看）。

每当您最终得到无限类型时，最好也添加类型签名：

cpfx'   :: [[Char]] -> Int -> [Char]
ifMatch :: [[Char]] -> Int -> Bool

突然，我们获得了额外的错误，两个

  | ifMatch (x:t) n = x!!n + cpfx' x (n+1)

 无法将预期类型“[Char]”与实际类型“Char”匹配
    预期类型：[[Char]]
      实际类型：[字符]
    在`(!!)'的第一个参数中，即`x'
    在`(+)'的第一个参数中，即`x !! n'

    没有 (Num [Char]) 的实例
      使用“+”引起的

和一个ifMatch：

  | x!!n == x!!n = ifMatch xs n

    无法将预期类型“[Char]”与实际类型“Char”匹配
    预期类型：[[Char]]
      实际类型：[字符]
    在‘ifMatch’的第一个参数中，即‘xs’
    在表达式中：ifMatch xs n

现在，错误cpfx'很简单：xis a [Char]，x !! nis a Char，并且想要将其 cons 到列表中，因此使用:代替+。此外，要应用cpfx'到t，不要x。这也修复了您的第二个错误。在ifMatch,x!!n == x!!n是多余的，并且xs有类型[Char]，因此没有正确的类型ifMatch。这也是一个错字：

  | x!!n == xs!!n = ifMatch t n

然而，既然我们修复了这些编译错误，你的程序真的有意义吗？特别是，您希望这行代码做什么：

ifMatch (x:xs) n = x!!n : cpfx' xs (n+1)

(x:xs)是你的话的清单。但是，您在每次迭代中都从您的单词中删除了一个单词，这显然不是您的意思。你要

ifMatch (x:xs) n = x!!n : cpfx' (x:xs) (n+1)

总的来说，我们得到以下代码：

cpfx :: [[Char]] -> [Char]
cpfx []     = []
cpfx [x]    = x
cpfx (x:xs) = cpfx' (x:xs) 0
 
cpfx' :: [[Char]] -> Int -> [Char]
cpfx' [x]    _ = []
cpfx' (x:xs) n
  | ifMatch (x:xs) n = x!!n : cpfx' (x:xs) (n+1)
  | otherwise = []

ifMatch :: [[Char]] -> Int -> Bool
ifMatch [x]      _ = True
ifMatch [x,y]    n = x!!n == y!!n
ifMatch (x:y:xs) n
      | x!!n == y!!n = ifMatch xs n
      | otherwise = False

使用 fold 的更简单方法

让我们通过commonPrefix为任何类型编写 a来使我们的函数更简单一些，但也更通用，它实现==：

commonPrefix :: (Eq e) => [e] -> [e] -> [e]
commonPrefix _ [] = []
commonPrefix [] _ = []
commonPrefix (x:xs) (y:ys)
  | x == y    = x : commonPrefix xs ys
  | otherwise = []

如果你不使用该符号，想到的e是Char一会儿。现在，有些词的常用前缀可以写成：

"hello" `commonPrefix` "hell" `commonPrefix` "hero"

现在的问题是，如果你想为一系列事情做一些事情，你通常使用fold：

foldl :: (a -> b -> a) -> a -> [b] -> a

foldl 应用于二元运算符、起始值（通常是运算符的左标识）和列表，使用二元运算符从左到右减少列表：

foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn

最后一个例子看起来和我们`commonPrefix`之前的代码一模一样！但是，我们没有起始值，因此我们将使用列表的第一个元素。幸运的是，已经有foldl1，它就是这样做的。因此，我们之前复杂的函数归结为：

commonPrefixAll :: (Eq a) => [[a]] -> [a]
commonPrefixAll = foldl1 commonPrefix

您应该记住的一点是：每当您想遍历列表中的多个元素以提供单个值时，请考虑是否真的有必要在每次迭代中查看所有元素。通常，一次只关注两个元素，然后使用正确的折叠就足够了。有关更多示例和信息，请参阅在 Real World Haskell 中通过集合计算一个答案部分。