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”匹配预期的类型：[[字符]]实际类型：[字符]在（（!!）'的第一个参数中，即x在`（+）'的第一个参数中，即`x !! n'
没有实例（（数字[字符]）因使用“ +”而产生
和ifMatch中的一个：

  | x!!n == x!!n = ifMatch xs n
无法将预期类型'[Char]'与实际类型'Char'相匹配预期的类型：[[字符]]实际类型：[字符]在“ ifMatch”的第一个参数中，即“ xs”在表达式中：ifMatch xs n
[现在，cpfx'中的错误非常简单：x是[Char]，x !! n是Char，并且想要将其限制在列表中，因此请使用:而不是+ ]。另外，您想将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
使用折叠的更简单方法

[通过为实现commonPrefix的任何类型编写==来使我们的功能更简单，但也使它更通用）>

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 f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
最后一个示例看起来与我们之前的`commonPrefix`行完全一样！但是，我们没有起始值，因此我们将使用列表的第一个元素。幸运的是，已经有foldl1可以做到这一点。因此，我们以前复杂的功能归结为：

foldl1
您应该从中记住的事情是：每当您要遍历列表中的多个元素以提供单个值时，请考虑是否真的有必要在每次迭代中查看所有元素。通常，一次只关注两个元素就足够了，然后使用正确的折叠。有关更多示例和信息，请参见commonPrefixAll :: (Eq a) => [[a]] -> [a]
commonPrefixAll = foldl1 commonPrefix
部分。

您可以避免很容易地使用显式递归：

Computing one answer over a collection in Real World Haskell

[

import Data.Maybe (isJust, fromJust)
commonPrefix = map fromJust . takeWhile isJust . map the . transpose' 

获取一个列表，如果列表的元素不同，则返回the，否则返回唯一元素：

Nothing

[

the :: Eq a => [a] -> Maybe a
the [] = Nothing
the (x:xs) 
  | and $ map (==x) xs = Just x
  | otherwise          = Nothing

类似于transpose'，但它将结果截断为最短列表的长度：

Data.List.transpose

[

transpose' xs = maybe [] id $ do
  ys <- mapM ht xs
  return $ (map fst ys) : (transpose' (map snd ys))
    where 
      ht [] = Nothing
      ht (x:xs) = Just (x,xs)

但transpose ["abc", "ab", "abcd"] == ["aaa","bbb","cc","d"]

您提到的行确实是一个问题。

[注意，transpose' ["abc", "ab", "abcd"] == ["aaa","bbb"]的参数为cpfx'，即所有事物的列表与(x:[])具有相同的类型，但是递归调用仅使用x。因此，您将收到无限类型错误：您正在尝试将x的类型标识为x的类型。 （具体来说，假设[x]是x。那么，您建议String的类型为x（由于参数的模式匹配）和String（如何使用[String]在递归调用中）。

我不太清楚您要做什么，但是由于x，您在同一行中也遇到了问题。这里，x!!n + ...是（可能）是x!!n，但是您正在使用Char运算符，该运算符未为+定义。您可能会说Char用于列表追加，除了++是not

列表之外，它是单个元素。因此，您可能的意思是

x!!n
或
[x!!n] ++ cpfx' ...

这里是思考问题的另一种方式：

假设您具有最长公共前缀的功能：

(x!!n) : cpfx' ...
您可以将其扩展到这样的列表：
lcp :: String -> String -> String
这种一般的递归模式称为折叠。

关于一个简单的函数呢：

cpfx [a]       = a
cpfx [a,b]     = lcp a b
cpfx [a,b,c]   = lcp (lcp a b) c
cpfx [a,b,c,d] = lcp (lcp (lcp a b) c) d
...

...并且工作正常：

import Data.List

cpfx xs = comp (reverse $ minimum xs) (map reverse xs)
 where comp ys xs
    | True == (all (==True) $ map (\x->isSuffixOf ys x) xs)
                  = reverse ys
    | ys  == []   = []
    | otherwise   = comp (tail ys) xs

Answer 2

您可以避免很容易地使用显式递归：

Answer 3

您提到的行确实是一个问题。

Answer 4

这里是思考问题的另一种方式：

Answer 5

关于一个简单的函数呢：